عبارت‌های منظم و زبان‌های منظم

زبان کدام‌یک از عبارت‌های منظم زیر، با بقیه فرق دارد؟

ماشین متناهی M به شکل زیر، مفروض است. L(M) معادل زبان تعریف شده توسط کدام مورد است؟

عبارت منظّم (regular expression) توصیف‌کننده زبان پذیرنده ماشین متناهی زیر کدام است؟ (منظور از ε رشته به طول صفر است.)

آیا می‌توان هر ماشین متناهی قطعی (DFA) را به DFA ای معادل تبدیل کرد به گونه‌ای که حالت شروع آن هیچ یال ورودی نداشته باشد؟ (یعنی تنها یال ورودی همان پیکان شروع باشد.)

تعداد حالات ماشین متناهی قطعی (DFA) کمینه زبان L = a^n b^n n ≤ 50 چندتاست؟

اگر L_1 = L(0^1^) ⊆ 0,1 ^ و L_2 = W_1 W_2 W_2 W_1 ∈ L_1 ، آنگاه L_2 به وسیلهٔ کدام‌یک از عبارات منظّم (regular expression) زیر تعریف می‌شود؟

اگر M یک ماشین متناهی حالت قطعی (DFA) باشد می‌گوییم دو رشته x و y نسبت‌به M با هم معادل‌اند، هرگاه (s,y)xrightarrow _M q ⇔ (s,x)xrightarrow _M q, که در آن s حالت شروع و q یک حالت دلخواه ماشین است.…

از میان چهار ادعای زیر، چند مورد درست است؟ الف) حداقل یک NFA بدون گذار ε و با فقط یک حالت نهایی وجود دارد که زبان مجموعه b^n : n ≥ 2 ∪ a را بپذیرد. ب) اگر L_1 و L_2 دو زبان باشند به‌گونه‌ای که L_2…