سوالات

فرض کنیم ‎ L_1 ‎ و ‎ L_2 ‎ زبان‌های منظم باشند. کدام مورد برای زبان ‎ L = w : w ∈ L_1, w^R ∈ L_2 ‎ صحیح است؟

کدام عبارت در زبان تولید شده توسط عبارت منظم r = (aa)^() b (bb)^() + a(aa)^() (bb)^() قرار ندارد؟

فرض کنید L = (01^()01^(+))^() و L' = ((0 + 00)1^(+))^() ، کدام گزینه درست است؟

L یک زبان منظم است. کدام‌یک از زبان‌های زیر لزوماً مستقل از متن است؟ L' = ww^Rw w ∈ L L'' = ww^Ru w, u ∈ L

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

گرامر G با قوانین تولید S → aSbb aaSbbb λ مفروض است. کدام عبارت در L(G) قرار دارد؟

فرض کنید L زبان همه رشته‌هایی با الفبای ۰ , ۱ است که تعداد صفرهایشان زوج است. زبان کدام‌یک از گرامرهای زیر برابر L است؟ الف- S → ۱S ۰S۰ ε ب- S → ۱S ۰T۰S ε , T → ۱T ε

npda با گراف انتقال زیر را درنظر می‌گیریم، کدام رشته در زبان این اتوماتای پشته‌ای قرار دارد؟ (α , β ; ω یعنی در شرایطی که با نماد بالایی پشته β است و α از ورودی خوانده می‌شود، رشته ω در پشته جایگزین…

دو تغییر زیر را روی هد (head) ماشین‌های تورینگ استاندارد اعمال و دو نوع ماشین جدید تعریف می‌کنیم: نوع اول: در هر حرکت (هر انتقال) مکان هد بتواند ثابت باشد، یک خانه به راست یا یک خانه به چپ حرکت کند.…

L و L' دو زبان هستند. چند تا از گزاره‌های زیر درست است؟ (توضیح نماد ≤ : برای دو زبان A و B می‌نویسیم A ≤ B هرگاه A تقلیل‌پذیر تورینگی به B باشد.) اگر L تصمیم‌پذیر باشد و L ≤ L' آن‌گاه L' تصمیم‌پذیر…

دو گرامر زیر را در نظر بگیرید. آنگاه کدام مورد صحیح است؟ G۱ : S → aS S → aSbS S → c G۲ : S₁ → T S₁ → U T → aTbT T → c U → aS₁ U → aTbU

زبان L کدام است؟ با این شرط که ε ∈ L ∀x,y ∈ L axby , bxay ∈ L ( n_a(x) : تعداد کاراکتر a در رشته x )

فرض کنید L ⊆ a ^() باشد، کدام جمله زیر صحیح است؟

برای کدام یک از زبان‌های زیر می‌توان یک NFA بدون ε ارائه داد که فقط دارای یک حالت پذیرش باشد؟

زبان‌های B_1= 1^k y 1^k y∈ 0,1 ^() و k≥ 1 و y شامل حداقل k تا یک و B_2= 1^k y 1^k y∈ 0,1 ^() و k≥ 1 و y شامل حداکثر k تا یک را در نظر بگیرید. کدام گزینه درست است؟

تفاوت ماشین‌های تورینگی که فقط زبان‌های منظم را می‌پذیرند با ماشین‌های تورینگ استاندارد کدام است؟

کدام‌یک از جملات زیر صحیح است؟

همهٔ عبارات زیر صحیح‌اند، به جز:

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

همه موارد زیر صحیح‌اند، به‌جز:

کدام‌یک از جملات زیر صحیح است؟

فرض کنید یک مجموعه متناهی مانند ∅ ≠ B که شامل اعداد صحیح است داده شده. حال هدف طراحی یک DFA روی الفبای ۰,۱ است به‌طوری که هر رشته مانند x = x_۱,…,x_n که به این DFA داده می‌شود در صورتی پذیرش می‌گیرد…

فرض کنید L_1 و L_2 منظم است. حال زبان‌های زیر را در نظر بگیرید: L'_1 = w w = u_1 v_1 u_2 v_2 … u_n v_n, u_1… u_n ∈ L_1, v_1… v_n ∈ L_2, u_i, v_i ∈ Σ L'_2 = w w = u_1 v_1 u_2 v_2 … u_n v_n, u_1… u_n ∈…

فرض کنید یک زبان روی الفبای Σ= a,b تعریف شده باشد به‌طوری که بین هر جفت a در رشته بتوان تعدادی فرد b یافت. DFA مینیمم روی این زبان شامل چند state است؟

به ازای هر state، k > ۰ و حروف الفبای ۰,۱ ، چه تعداد DFA با State، K می‌توان ارائه کرد؟

زبان معادل با گرامر زیر کدام است؟ S → Ax By A → By Cw B → x Bw C → y

رابطهٔ بازگشتی زیر چه زبانی را توضیح می‌دهد؟ Σ = a, b λ ∈ L ∀ x ∈ L ⇒ axab ∈ L, bx ∈ L

بر اساس چه مقداری از w ، L منظم می‌شود؟ L = a^n w b^n n ≥ ۰

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

همه جملات زیر صحیح‌اند، به جز:

فرض کنید L زبان عبارت منظم r = (0+1)^() 0 (0+1)(0+1) باشد. از دو عبارت α = ۱۱۰۱۰۱۱۰۱۰۱۱۰۰۰۱۰۰ و β = ۰۱۰۱۱۱۰۱۱۱۰۱۰۱۱ ، کدام عضو زبان L است؟

فرض کنید L زبان گرامر زیر باشد: S → TbT T → aTb bTa TT λ از دو عبارت α = b aa bb a bb a bb aa bb و β = bbb ab aa b aaa b b ، کدام عضو زبان L است؟

فرض کنید L زبان گرامر زیر باشد: S → BA A → ∘∘ A1 ∘ B → ∘ B ∘ از دو عبارت α = ∘^(1∘)1^21 و β = ∘^221^(1∘) کدام عضو زبان L هست؟

فرض کنید: L_1 = w ∈ a, b ^ w = w^R L_2 = w ∈ a, b ^ n_ab(w) = n_aa(w) از این دو زبان کدام منظم است؟

از دو عبارت زیر کدام صحیح است؟ I: اگر تعدادی متناهی رشته از یک زبان منظم حذف کنیم حاصل یک زبان منظم خواهد بود. II: اگر تعدادی متناهی رشته به یک زبان غیرمنظم اضافه کنیم حاصل یک زبان غیرمنظم خواهد بود.

فرض کنید L زبان گرامر زیر با متغیر شروع S باشد: S → aAS S → a A → SbA A → SS A → ba از دو عبارت زیر کدام صحیح است؟ I: برای هر w ∈ L ، پنج رشته u, v, x, y, z وجود دارند که w = uvxyz و vy ≥ ۱ و برای هر…

فرض کنید زبان L با PDA به شکل زیر باشد که Σ = a,b الفبای ورودی و Γ = x , z الفبای پشته و z نماد بالایی پشته است. با قرار گرفتن کدام‌یک از دو مقدار a یا b به جای y در w = a^۱۴۰۴y b^۲۱۰۵ ، رشته w حاصل…

فرض کنید L زبان ماشین تورینگ زیر باشد: (نمودار حالت‌ها با حالت آغازین q_۱ و حالت‌های q_۲,…,q_۶,q_accept,q_reject روی الفبای نوار ∘, x, sqcup . ماشین نخستین ∘ را حذف می‌کند و سپس به‌طور مکرر نوار را…

فرض کنید M یک ماشین تورینگ معمولی است با این تفاوت که امکان حرکت به چپ را ندارد اما می‌تواند در همان خانه بماند. کدام مورد درخصوص M درست است؟

فرض کنید زبان L، زبان dfa زیر باشد: (در نمودار: حالت آغازین q_1 است؛ گذارها: q_1xrightarrow a q_2 ، q_1xrightarrow b q_3 ، q_2xrightarrow a q_2 ، q_2xrightarrow b q_3 ، q_3xrightarrow a q_4…