حل تشریحی سوالات نظریه زبان‌ها و ماشین‌ها - کنکور ارشد مهندسی کامپیوتر 1402

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

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

تعداد حالات ماشین متناهی قطعی (DFA) کمینه زبان $L=\left\{a^n{b}^n|n\le 50\right\}$ چندتاست؟

اگر $L_1=L\left(0^{\ast }{1}^{\ast }\right)\subseteq {\left\{0,1\right\}}^{\ast }$ و $L_2=\left\{W_1{W}_2|W_2{W}_1\in L_1\right\}$ انگاه $L_2$ به وسیله کدام یک از عبارات منظم (regular experession) زیر تعریف میشود؟

به ازای دو عرر صحیح و ثابت 0<r و 0<q کدام یک از زبان های زیر مستقل از متن (context-free) بوده ولی منظم (regular) نیست ؟