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

زبان‌های $L1=ø$ و L2={a} را در نظر بگیرید. پاسخ $L1L{2}^{\ast }\cup L{1}^{\ast }$ برابر با کدام مورد است؟

$DFA$زیر را بنام A در نظر بگیرید، کدام یک از گزاره‌های زیر نادرست است؟

$-a$مکمل L(A) زبان مستقل از متن است.

$L(A)=L((11^{\ast }0+0)(0+1{)}^{\ast }{0}^{\ast }{1}^{\ast }-b$

$-c$برای زبان پذیرفته شده به وسیله A, A یک DFA کمینه است

$A-d$ همه رشته‌های تعریف شده رئی {1 , 0} با طول حداقل 2 را میپذیرد.

زبان L={ab , aa , baa} را در نظر بگیرید. کدام یک از رشته‌های زیر در $L^{\ast }$ وجود دارد؟

الف- abaabaaabaa

ب- aaaabaaaa

ج- baaaaabaaaab

د- baaaaabaa

کدام یک از مسائل زیر تصمیم ناپذیر است؟

الفبای A={a,b} را در نظر بگیرید. زبان L شامل تمامی عبارات منظمی است که از الفبای A قابل ساخت هستند. کدام گزینه صحیح است؟

بر الفبای A={a,b} ، دو زبان زیر را تعریف کرده‌ایم:

$L_1=\{\omega |\omega$ has exactly two a's}

$L_2=\{\omega |\omega$ has exactly two b's}

اگر L زبان پذیرفته شده توسط ماشین حالت متناهی زیر باشد، کدام گزینه درست است؟

گرامر زیر را در نظر بگیرید:

$A\to$ D A D | B

$B\to$ 0 C 1|1 C 0

$C\to$ D C D|D|$\epsilon$

1 | 0$D\to$

زبانی که گرامز فوق تولید میکند کدام است؟

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

زبان‌های $L_1=\left\{x\#y|x,y\in {\left\{0,1\right\}}^{\ast },x\ne y\right\}$ و $L_2=\left\{x\#y|x,y\in {\left\{0,1\right\}}^{\ast },x=y\right\}$ را در نظر بگیرید. در این خصوص کدام مورد درست است؟

در خصوص زبان $L=\left(a^n{b}^n{a}^m{b}^m:n\ge 5,m\ge 10\right)$ کدام مورد درست است؟