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

کدام یک از زبان های زیر مستقل از متن هستند؟
۱) [tex]L=\left\{a^{2n}|n=3k\right\}[/tex]
۲) [tex]L=\left\{a^{2^{n}}:3n=k\right\}[/tex]
۳)[tex]L=\{a^n\backslash n>100\: or\: n\: is\: prime\}[/tex]
۴) هیچکدام

من فک کنم هیچکدام

منم فکر میکنم هیچکدام هست
اولی و دومی چون توانی از 2n دارن یعنی رشته های زوج که ما میتونیم رشته ی فرد رو هم با لم تزریق اضافه کنیم
پس مستقل از متن نیست..
برای سومی هم رشته رو میتونیم نقض کنیم و اعداد غیر اول رو هم تولید کنیم...
هیچ کدام

سلام.
گزینه 1 رشته های بطول مضرب 6 نیازه. منظمه.
گزینه 2 مستقل از متن نیست.
گزینه 3 منظمه. میشه با حدوداً 100 حالت پیاده سازیش کرد.

(16 دى 1391 06:51 ب.ظ)A.nonymous نوشته شده توسط: [ -> ])

علت منظم بودنش اینه که در عبارت or به کار برده؟ یعنی گفته یا بیشتر از 100 یا اول باشد ، درسته؟

(10 بهمن 1391 02:25 ب.ظ)fatima1537 نوشته شده توسط: [ -> ]

(16 دى 1391 06:51 ب.ظ)A.nonymous نوشته شده توسط: [ -> ])

علت منظم بودنش اینه که در عبارت or به کار برده؟ یعنی گفته یا بیشتر از 100 یا اول باشد ، درسته؟

اجتماع دو زبانه که a^n ; n>100 منظمه ولی قسمت دوم که منظم نیست. چون عدد اول رو نمی تونه تشخیص بده و تعدادش هم متناهی نیست پس منظم نیست. مستقل از متن هم نیست. فقط با ماشین تورینگ پذیرفته میشه.

(10 بهمن 1391 02:54 ب.ظ)egm1176 نوشته شده توسط: [ -> ]

(10 بهمن 1391 02:25 ب.ظ)fatima1537 نوشته شده توسط: [ -> ]

(16 دى 1391 06:51 ب.ظ)A.nonymous نوشته شده توسط: [ -> ])

علت منظم بودنش اینه که در عبارت or به کار برده؟ یعنی گفته یا بیشتر از ۱۰۰ یا اول باشد ، درسته؟

اجتماع دو زبانه که a^n ; n>100 منظمه ولی قسمت دوم که منظم نیست. چون عدد اول رو نمی تونه تشخیص بده و تعدادش هم متناهی نیست پس منظم نیست. مستقل از متن هم نیست. فقط با ماشین تورینگ پذیرفته میشه.

منظمه چون میتونید برای DFA رسم کنید، اگه n بیشتر از 100 باشه، که رشته پذیرش میشه، برای n های کمتر از 100، تعداد اعداد اول کوچکتر از 100 رو میتونیم بشماریم.

اساتید درست میفرمایند.بله حق با شماست سرکنکور با دقت میخونیم