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

کدام یک از گزاره‌های زیر درست است؟

سه زبان $L_{3,}{L}_{2,}{L}_1$ با تعاریف زیر مفروضند، کدام گزاره صحیح است؟

$L_1=\left\{w{o}^n|w\in {\left\{a,b\right\}}^{\ast },n_a\left(w\right)=n_b\left(w\right)=n,\left|w\right|=2n\right\}$

$L_2=\left\{w{o}^n|w\in {\left\{a,b\right\}}^{\ast },\left|w\right|=n\right\}$

$L_3=\left\{w{o}^n|w\in {\left\{a,b\right\}}^{\ast },\left|w\right|=n\right\}$

گرامر زیر چه زبانی را تولید میکند؟ ($\epsilon$ بیانگر رشته تهی است)

$G:S\to S_{1}B$

$S_1\to a{S}_{1}b$

$bB\to bbbB$

$a{S}_{1}b\to aa$

$B\to \epsilon$

از میان چهار جمله زیر، چه تعداد از آن‌ها صحیح است؟

الف- اشتراک دو زبان بازگشتی، لزوما یک زبان بازگشتی است.

ب- اگر h(L) (تصویر همومورفیک L) منظم باشد میتوان نتیجه گرفت خود L نیز منظم است.

ج- اجتماع دو زبان مستقل از متن قطعی، خود یک زبان مستقل از متن قطعی است.

د- زبان‌های شمارش پذیر بازگشتی تحت عملیات مکمل گیری بسته هستند.

اگر M یک ماشین حالت متناهی قطعی (DFA) باشد میگوییم دو رشته x و y نسبت به M باهم معادلند. هرگاه که در ان s حالت شروع و q یک حالت دلخواه ماشین است. کلاس‌های هم ارزی رشته ها نسبت به ماشین رو به رو کدام است.