نظریه زبان‌ها و ماشین‌هاTheory of Computation

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

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

درخصوص گرامر مستقل از متن از متن زیر، کدام مورد درست است؟ S → A0 S1 1 A → 1S 1A 0

فرض کنیم L_1 ، L_2 و L_3 سه زبان مستقل از متن دلخواه باشند. آنگاه کدام مورد زیر درست است؟ (منظور از L' متمم مجموعه‌ای L است.)

کدام یک از مسائل زیر، در مورد یک اتوماتون پشته‌ای غیرقطعی (NPDA) دلخواه به‌نام M، تصمیم‌پذیر (decidable) است؟

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

کدام مورد، درست است؟

کدام یک از زبان‌های زیر، مستقل از متن نیست؟

کدام مورد، درست است؟

کدام مورد، زبان تولیدشده توسط گرامر زیر را توصیف می‌کند؟ S → aSc aS A A → bAcc bA bAc ε

عبارت منظّم (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) زیر تعریف می‌شود؟

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

چه تعداد از گزاره‌های زیر درست است؟ هر زبان تشخیص‌ناپذیر تورینگ، تصمیم‌ناپذیر است. مجموعه همه زبان‌های نامنظم روی یک الفبا، یک مجموعه شمارای نامتناهی است. مجموعه همه ماشین‌های تورینگ روی یک الفبا، یک…

زبان پذیرفته شده توسط پذیرنده پشته‌ای PDA روبه‌رو، کدام گزینه است؟ ( N_a(w) تعداد حرف a در رشته w را مشخص می‌کند.)

زبان L = a^(2^n) n ≥ ۰ را درنظر بگیرید. برای تولید زبان بالا گرامر زیر پیشنهاد شده است. ( S متغیر شروع و a تنها حرف الفبا است.) G: S, → [Ra] a; Ra, → aaR; aL, → La; aH, → ?a; R, → L] H; [L, → [R; [?…

فرض کنید L۱ و L۲ زبان‌های مستقل از متن (context−free) و R زبانی منظم (regular) باشند. کدام گزینه، لزوماً زبانی مستقل از متن نخواهد بود؟

گرامر روبه‌رو کدام‌یک از زبان‌های زیر را توصیف می‌کند؟ S → aSd A B A → aAc C B → bBd C C → bCc ε

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

سه زبان L_1, L_2, L_3 با تعاریف زیر مفروضند. کدام گزاره صحیح است؟ L_1 = wo^n w ∈ a,b ^, n_a(w) = n_b(w) = n, w = 2n L_2 = wo^n w ∈ a,b ^, w = n L_3 = wo^n w ∈ a,b ^, n_a(w) = n یا w = n

گرامر زیر چه زبانی را تولید می‌کند؟ ( ε بیانگر رشتهٔ تهی است.) G: , S → S_1 B ;, S_1 → a S_1 b ;, bB → bbb B ;, a S_1 b → aa ;, B → ε

از میان چهار جملۀ زیر، چه تعداد از آن‌ها صحیح است؟ الف- اشتراک دو زبان بازگشتی، لزوماً یک زبان بازگشتی است. ب- اگر h(L) (تصویر همومورفیک L ) منظم باشد می‌توان نتیجه گرفت خود L نیز منظم است. ج- اجتماع…

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

زبان L و ماشین پشته‌ای (PDA) زیر را در نظر بگیرید. برای آنکه این PDA به درستی پذیرندهٔ زبان L باشد، کدام‌یک از شرایط زیر لازم و کافی است؟ نمودار PDA. سه حالت: s (حالت شروع)، p و q (حالت نهایی، با…

زبان‌های L_1 و L_2 زیر را در نظر بگیرید. کدام مورد درست است؟ L_1 = 1^n 2^n 3^n n ≥ ۰ L_2 = 1^n 2^n 3^n 4^n n ≥ ۰

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

کدام‌یک از مسائل زیر برای یک ماشین تورینگ دلخواه تصمیم‌پذیر (decidable) هستند؟

درخصوص کلاس زبان‌های مستقل از متن قطعی (DCFL) (Deterministic Context Free Languages) کدام مورد درست است؟