تالار گفتمان مانشت

سلام دوستان میشه به این سوال توجه کنین
مقسمی میگه 2 درسته پوران میگه جواب درستی نداره اما مشخصه که گزینه سه منظمه چون همون a*b* دیگه اما گزینه 1 و 2 رو نمیدونم کمکم کنین
با سپاس

فک میکنم گزینه دو درست هست چون باید حتما بین تعداد a,b کنترل برقرار باشه
گزینه 3 که حتما منظم هستش دلیلش هم اینه که رشته هایی که این زبان می پذیرند این هستش که هر چقدر a اول بیاد و هرتعداد هم b بعدش و اون توان های n که برای a,b گذاشته گمراه کننده هست پس گزینه 3 منظم هستش پس یه DFA میشه براش رسم کرد در نتیجه گزینه 4 هم رد میشه
اما گزینه 1 رو بررسی کنیم ببین درسته که در رشته های مربوط به این زبان اول باید تعداد a,b مساوی باشه اما بعدش هر ترکیبی از a,b میتونه بیاد و قانون مساوی بودن تعداد a,b شکسته میشه مثلا aabbb یا aabba پس میشه یه ماشین متناهی(dfa) براش رسم کرد
اما گزینه 2 نمیشه چون اول b میاد حالا به ترتیب a وb و سپش a مهم مساوی بودن تعداد a,b های وسط رشته هستش که هیج جوره نمیشه این وابستگی رو ازبین برد یعنی مثال نقضی نمیتونی بیاری

میشه استفاده از لم تزریقو واسم توضیح بدید /
انتخاب x,y,z بر چ اساسیه؟
سپاس فراوان

ایا این زبان منظمه ؟ تمرین پیتر لینزه
تو حل المسایلش بدون توضیحی گفته خیر اما من تونستم واسش nfa بکشم ؛ نمیدونم دیگه والا!

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

واسه زبان بالا نمیشه fa کشید! این تعداد دوطرف به هم وابسته هستند و کار پشته هست.این زبانو نمیشه خلاصه کرد تا به صورت عبارت منظم در بیاد.
اگر nfa کشیدید شکلشو بگذاریدو این زبان نامنظمه!!

بفرما

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

ببین دوست من شما به n توجه نکردی همه موضوع همینه الان من با این dfa شما رشته abbbaabbababa
در صورتی که باید تعداد bbaa با ba مساوی باشند (بار رنگ قرمز مشخص کردم)ولی مساوی نیست شما مثال غلط خوبی رو برای درک زبان های منظم حل کردی و مطمئن هستم اگه اشتباهتو بفهمی خیلی خوب زبان های منظم و غیر منظم رو درک میکنی.
من الان که خواستم nfa شما رو رد کنم دنبال مثال نقض گشتم اون هم این هست تو این nfa به مساوی بودن تعداد bbaa‌ها با ba‌ها توجه نکردی و این دقیقا همون نیاز به حافظه یا پشته هستش که ماشین های متناهی ندارند پس این زان منظم نیست.باید از ماشین پشته ای استفاده کنی
زبان ماشین شما این هست که منظم هم هستش
ab(bbaa)*bba(ba)*j

حق با آقا جواده حتما نیاز به پشته داریم.

بله کاملا حق با شماست
از راهنماییتون سپاسگزارم

ممکنه درباره گزینه 3 این سوال بیشتر توضییح بدید که چرا این زبان همون a*b* هستش ؟ من درست درک نمی کنم ممنون .

[tex]a^{3}b^{4}=a(a^{2}b^{2})b^{2}[/tex]

یعنی هر رشته ای که به فرم [tex]a^{*}b^{*}[/tex]

رو میشه به صورت [tex]a^{*}a^{n}b^{n}b^{*}[/tex]

[tex]a(a^{2}b^{2})b^{2}=a^{3}b^{4}[/tex]


نوشت یعنی این دو معادل هم هستند.

و این به خاطر اینه که [tex]a^{*} , a^{n}[/tex] کنار هم هستند و مجموع این دو نیز خود [tex]a^{*}[/tex] است در مورد b نیز به همین صورت است .

اگر [tex]a^{*} , a^{n}[/tex] کنار هم نباشند دیگر مورد بالا برقرار نیست مثل گزینه 2 .