چرا در سوال ۶۲ L1 و L3 منظم هستن؟
چرا در سوال اول L(G زیر مجموعه L1 هست؟
من نمیتونم موردی رو پیدا کنم که L1 اونو قبول کنه اما L(G اونو قبول نکنه!
من هرچی برا خودم مثال زدم زبان L1 با زبان گرامر یکی شد.
فکر میکنم گرامر a^n b^2n a^n قبول نمیکنه اما L1 این رشته رو میپذیره
لطفا راهنمایی کنید
جواب سوال دوممو فهمیدم پس فقط سوال ۶۲ میزارم
(۱۸ بهمن ۱۳۹۰ ۰۷:۵۸ ب.ظ)homa نوشته شده توسط:(18 بهمن ۱۳۹۰ ۰۷:۳۱ ب.ظ)narges_r نوشته شده توسط: چرا در سوال اخر L1 و L3 منظم هستن؟
چرا در سوال اول L(G زیر مجموعه L1 هست؟
من نمیتونم موردی رو پیدا کنم که L1 اونو قبول کنه اما L(G اونو قبول نکنه!
لطفا راهنمایی کنید
من هم هرچی برا خودم مثال زدم زبان L1 با زبان گرامر یکی شد.
سوال هم گذاشتم
فکر میکنم گرامر a^n b^2n a^n قبول نمیکنه اما L1 این رشته رو میپذیره
در مورد گرامر L2 ما وابستگی توانی بین جمله‌ها داریم جمله اخر با دو تای اولی
اما در مورد گرامر L1 و L3 هر کدوم از جمله‌ها میتونن به تعداد دلخواه بیان و نه نیاز به حافظه داریم و نه وابستگی توانی دارن
درمورد سوال قبل چون S->SS نداریم رشته هایی مشابه aaabbbaaabbb و امثالش که برای تولید به این قاعده احتیاج دارن رو نمیشه با گرامر تولید کرد.
درمورد سوال ۶۲ اگه آلفا و گاما رو نال بگیریم و مقادیر i,j رو ۰ یا ۱ با توجه به فرضشون درنظر بگیریم که مغایرت هم نداشته باشه، در این صورت L1,L2 میشن سیکما استار و L3 میشه سیکما پلاس. همشون منظمن.
(۱۸ بهمن ۱۳۹۰ ۰۸:۴۸ ب.ظ)Lakikharin نوشته شده توسط: درمورد سوال قبل چون S->SS نداریم رشته هایی مشابه aaabbbaaabbb و امثالش که برای تولید به این قاعده احتیاج دارن رو نمیشه با گرامر تولید کرد.ولی L2 منظم نیست چون باید تعداد جمله‌ی آخر بر اساس دو رشته‌ی قبلی باشه و نه بیشتر و نه کمتر
درمورد سوال ۶۲ اگه آلفا و گاما رو نال بگیریم و مقادیر i,j رو ۰ یا ۱ با توجه به فرضشون درنظر بگیریم که مغایرت هم نداشته باشه، در این صورت L1,L2 میشن سیکما استار و L3 میشه سیکما پلاس. همشون منظمن.
خوب مثلادر L1 الفا و گاما باید تعدادشون یکی باشه، چرا میگید که وابستگی توانی ندارند؟
گفتم که اگه آلفا و گاما رو نال درنظر بگیرین تمام رشته های زبانو میشه باهاش ساخت. با قراردادن j=0 رشته نال و با قرار دادن j=1 بقیه رشته‌ها با توجه به بتا تولید میشه..
فرض کنید زبانی داریم که رشته های بفرم W^i رو قبول میکنه که W سیکما استار و i بزرگتریامساوی یکه. میخایم ببینیم که این زبان چه رشته هایی رو قبول میکنه. W و WW و WWW و WWWW و WWW...WWW رشته هایی هستن که زبان تولید میکنه. اگه توجه کنید بخاطر سیکما استار بودن W تمام رشته هایی که از چند W تشکیل شده رو هم شامل میشه. یعنی تمام رشته هایی رو که میشه با WW یا WWWWW و ... ساخت رو با W هم میشه ساخت.
توی این سوال هم تونستیم رشته هارو به فرمی بنویسیم که تمام رشته های دیگه رو شامل بشه. یعنی رشته ای وجود نداشته باشه که توی زبان باشه و با یکی از چند حالت محدود مشخص نشه ساخت. البته باید توجه کنیم که این حالات مشخص با قرار دادن مقادیر لازم برای متغیرهاش ساخته بشن. تونستیم برای این رشته‌ها یه ماشین جدیدی پیدا کنیم که تمام حالات دیگه رو پوشش بده و میتونیم برای اون یه dfa بکشیم. پس منظمه.
(۱۹ بهمن ۱۳۹۰ ۱۲:۴۵ ق.ظ)پشتکار نوشته شده توسط: در مورد سوال ۵۸ اگه دقت کنید زبان L1 مثلا رشته aaaaaaabbbbbbb رو هم می پذیره چون تعداد a,b هاش یکسانه در حالیکه گرامر این رشته رو نمی پذیره و برای رشته های خاصی از L1 فقط پذیرش داره.
پس زبان گرامر زیرمجموعه زبان L1 خواهد بود.
قانون
aSb<----S
میتونه این رشته ایی که گفتین رو تولید کنه
aabbaabb
این یکی رو که دیگه فکر نکنم
(۱۹ بهمن ۱۳۹۰ ۰۲:۴۹ ق.ظ)Lakikharin نوشته شده توسط: گرامر نمیتونه این رشته رو تولید کنه. چون خطیه. aaabbbaaaabbbbaaabbb یا هر رشته ای که باید با S->SS تولید بشه.
بازم درمورد ۶۲ باید بگم همشون منظم هستن. دلیلشم گفتم.
میشه مبتدی‌تر و واضح‌تر بگید؟
چرا میگید بعضی‌ها رو نال کنیم؟
از روی چه منطق و حسابی
یه استادی هم همین حرف شما رو زد ولی من این موضوع رو کامل درک نمی کنم
متشکرم
(۱۹ بهمن ۱۳۹۰ ۱۱:۰۵ ق.ظ)HRZ نوشته شده توسط: aaabbbaaaabbbbaaabbb رو که میشه تولید کرد
متشکر. مثل اینکه اشتباه مثال زدم. همون aaabbbaaaaaabbbbbb رو درنظر بگیرین. منظورم از این مثال این بود که رشته از چندجا گسترش پیدا کنه.
(۱۹ بهمن ۱۳۹۰ ۰۴:۴۳ ب.ظ)پشتکار نوشته شده توسط:(19 بهمن ۱۳۹۰ ۰۲:۴۹ ق.ظ)Lakikharin نوشته شده توسط: گرامر نمیتونه این رشته رو تولید کنه. چون خطیه. aaabbbaaaabbbbaaabbb یا هر رشته ای که باید با S->SS تولید بشه.
بازم درمورد ۶۲ باید بگم همشون منظم هستن. دلیلشم گفتم.
میشه مبتدی‌تر و واضح‌تر بگید؟
چرا میگید بعضی‌ها رو نال کنیم؟
از روی چه منطق و حسابی
یه استادی هم همین حرف شما رو زد ولی من این موضوع رو کامل درک نمی کنم
متشکرم
فرض کنید زبانی داریم که رشته های بفرم W^i رو قبول میکنه که W سیکما استار و i بزرگتریامساوی یکه. میخایم ببینیم که این زبان چه رشته هایی رو قبول میکنه. W و WW و WWW و WWWW و WWW...WWW رشته هایی هستن که زبان تولید میکنه. اگه توجه کنید بخاطر سیکما استار بودن W تمام رشته هایی که از چند W تشکیل شده رو هم شامل میشه. یعنی تمام رشته هایی رو که میشه با WW یا WWWWW و ... ساخت رو با W هم میشه ساخت.
توی این سوال هم تونستیم رشته هارو به فرمی بنویسیم که تمام رشته های دیگه رو شامل بشه. یعنی رشته ای وجود نداشته باشه که توی زبان باشه و با یکی از چند حالت محدود مشخص نشه ساخت. البته باید توجه کنیم که این حالات مشخص با قرار دادن مقادیر لازم برای متغیرهاش ساخته بشن. تونستیم برای این رشته‌ها یه ماشین جدیدی پیدا کنیم که تمام حالات دیگه رو پوشش بده و میتونیم برای اون یه dfa بکشیم. پس منظمه.