سوالات

فرض کنیم L یک زبان دارای DFA بر الفبای Σ باشد و a ∈ Σ . کدام مورد درخصوص زبان L' = w ∈ Σ^ : wa ∈ L درست است؟

‏DFA زیر، بر Σ = a, b, c مفروض است. اگر t تعداد رشته‌های به طول ۳ یا کمتر باشد که توسط این DFA پذیرفته می‌شود، کدام مورد درخصوص t درست است؟ خودکار دارای حالت‌های q_1, q_2, q_3, q_4 است. حالت شروع q_1…

اگر L زبان عبارت منظم r=(0+10)^ 1^ باشد و α=1001010110111 و β=0101000110011 ، کدام مورد درست است؟

دو زبان L_1 و L_2 را بر Σ = 0, 1 به‌صورت زیر، درنظر می‌گیریم: L_1 = 0^n 1 0^n 1 0^n : n ≥ 0 L_2 = w : w تعدادی فرد 0 دارد از این دو زبان، کدام منظم است؟

دو زبان L_1 و L_2 روی الفبای Σ = a, b را به‌صورت زیر در نظر می‌گیریم: L_1 = w : n_a(w) = n_b(w) شامل زیررشته‌ی aab نیست L_2 = a^n b^j a^i b^n : n, i, j ≥ 0 از این دو زبان، کدام مستقل از متن است؟

دو زبان L_1 و L_2 را بر Σ = a, b به‌صورت زیر در نظر می‌گیریم: L_1 = a^n b^j a^n b^j : n, j ≥ 0 L_2 = a^n b^j : 0 ≤ n ≤ j^2 از این دو زبان، کدام مستقل از متن است؟

گرامر G با متغیر شروع S بر Σ = a, b, c با قوانین تولید زیر را درنظر می‌گیریم: S → XY W X → aXb ε Y → cY ε W → aWc Z Z → bZ ε با قرار گرفتن کدام‌یک از دو مقدار b یا c به‌جای α در w = a^1402 b^1401 α…

اتوماتای پشته‌ای زیر مفروض است. اگر α = 000011 و β = 000101010 ، کدام‌یک از این دو رشته، توسط این اتوماتا پذیرش می‌شود؟ اتوماتا دارای حالت‌های q_0, q_1, q_2, q_3, q_4 است که q_0 حالت شروع و q_4 تنها…

فرض کنیم زبان‌های L_A ⊆ Σ^() و L_B ⊆ Σ^() توسط DFAهای A=(Q_A,Σ,δ_A,q_0,F_A) و B=(Q_B,Σ,δ_B,q_0',F_B) داده شده‌اند و Σ= 0,1,2 . اتوماتای C را با زبان L_C به‌صورت زیر در نظر می‌گیریم: C=(Q_A× Q_B, Σ…

ماشین تورینگ M با جدول انتقال زیر داده شده است (هر درایه (حالت بعدی، نماد نوشته‌شده، حرکت)؛ نشانگر ابتدای نوار و # نماد تهی است): state symbol 0 1 #…

فرض کنیم L زبان منظم عبارت زیر باشد: r = b^()ab^()ab^()ab^() (b^()ab^()ab^()ab^()ab^()ab^()ab^())^() با قرار گرفتن کدام مقدار به‌جای m در عبارت w = b^۷۰۰a^۷۰۰(ab)^۷۰۰ma حاصل در L قرار می‌گیرد؟

عبارت منظم اتوماتون زیر چیست؟ (در شکل، نماد ∘ همان ۰ است.)

فرض کنیم هر بلوک از صفرهای متوالی در w اندازه زوج داشته باشد (مثلاً ۰۰۰۰۰۱۰۰ در L_1 هست ولی ۰۰۱۱۰ در L_1 نیست.) و L_1 = w ∈ ۰,۱ و L_2 = ۰^(۳^n) n ≥ ۰ . کدام‌یک از دو زبان فوق منظم است؟

گرامر G = (V, ∑, R, S) با مجموعه متغیرهای V = S, W, X, Y, Z ، متغیر شروع S ، ∑ = a, b, c و قوانین زیر مفروض است: S → XY W X → aXb ε Y → cY ε W → aWc Z Z → bZ ε با قرار گرفتن کدام‌یک از دو مقدار b یا…

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

فرض کنید: L_1 = w # x # w^R / w, x ∈ 0,1 ^(), w = x L_2 = x # y / x, y ∈ 0,1 ^(), x = 2 y کدام‌یک از دو زبان فوق مستقل از متن است؟ ( # یک حرف الفباست. همچنین برای هر رشته مانند z تعداد حروف z را با z…

از روی DFAهای D_1 و D_2 بر اساس ضرب دکارتی، DFAای به نام D ساخته می‌شود که: D_1 = ⟨ Q_1, ∑, δ_1, q_1^0, F_1 ⟩ D_2 = ⟨ Q_2, ∑, δ_2, q_2^0, F_2 ⟩ ⇒ D_1 × D_2 = ⟨ Q_1 × Q_2, ∑, δ, ⟨ q_1^0, q_2^0 ⟩, F ⟩…

اگر w = xWz در این‌صورت x را یک قطعه اولیه w و z را یک قطعه انتهایی w می‌گوییم ( x و W و z کاملاً دلخواه هستند بنابراین می‌توانند رشته تهی نیز باشند.) فرض کنید: P(L) = x x قطعه اولیه رشته‌ای مانند w…

فرض کنیم M ماشین تورینگ زیر باشد: ( B یعنی بلانک، که در برخی منابع با λ نشان داده می‌شود. اما b یک حرف الفباست.) اگر L(M) زبان این ماشین تورینگ باشد، کدام‌یک از موارد زیر درست است؟ الف) aaa bb aa bb…

گرامر مقابل را در نظر بگیرید: S → AB A → a A → BaB B → bbA کدام گزینه نادرست است؟

فرض کنیم زبان L گرامر زیر باشد (S متغیر شروع): S → aSaa B B → bB λ به‌ازای کدام مقدار برای x رشته‌ی aaa x b aaa a a a عضو L است؟

فرض کنیم L_1 و L_2 به‌ترتیب زبان دو گرامر G_1 و G_2 باشد ( S متغیر شروع): G_1 : S → aSbS bSaS λ G_2 : S → aSa bSb λ کدام‌یک از این دو زبان منظم هستند؟

دو عبارت زیر را درنظر بگیرید: الف) فرض کنیم M یک NFA (اتوماتای متناهی نامعین) باشد و ′M یک NFA کاملاً شبیه M با این تفاوت که حالت‌های پایانی (پذیرش) ′M غیرپایانی و حالت‌های غیرپایانی ′M در M حالت‌های…

فرض کنیم L زبان گرامر زیر باشد (S متغیر شروع): S → aA bB A → aB bS λ B → bA aS کدام‌یک از دو رشته x = a^۱۲ b^۶ a^۶ و y = b^۱۵ a^۱۰ b^۸ در L قرار دارد؟

به‌ازای کدام مقدار x عبارت b^7a^5b^3xa^5 در زبان عبارت منظم r = b^()ab^()(b^()ab^()ab^()ab^()ab^()ab^())^() قرار می‌گیرد؟

فرض کنیم L زبان NFA زیر باشد. با قراردادن کدام‌یک از دو مقدار ۰ و ۱ به‌جای x در عبارت ۱۱۱۱۰۰۱۰x۱۰۰۰۱۱ عبارت حاصل در L قرار می‌گیرد؟

کدام‌یک از دو زبان زیر مستقل از متن است؟ L_1 = a^n c^m b^n n > m ≥ 0 L_2 = a^n b^m c^k k ≠ n + m, n, m, k ≥ 0

می‌توان با شرایط گفته شده در لم تزریق تجزیه کرد. مقدار p منحصر به فرد نیست چون اگر p طول تزریق L باشد، هر عدد بزرگ‌تر از p نیز هست. همواره می‌توان کوچک‌ترین طول تزریق را یافت. کوچک‌ترین طول تزریق…

فرض کنید M ماشین تورینگ زیر باشد: اگر ‫α = ۰^۱۶‬ و ‫β = ۰^۱۷‬ کدام‌یک از این دو رشته توسط M پذیرفته می‌شود؟

الف) یک Mid PDA یک PDA توسعه‌یافته است که می‌تواند وسط پشته را بخواند. در واقع تابع انتقال در Mid PDA تابع چهار چیز است: نماد ورودی، نماد بالایی پشته، حالت فعلی ماشین و نماد وسط پشته. ( اگر پشته k…

فرض کنید: L_1 = 0^2n1^n n ≥ 0 L_2 = a^i b^j c^k i + j = k کدام گزینه در مورد این دو زبان درست است؟

موارد زیر را در نظر بگیرید: I) کلاس زبان‌هایی که توسط NFA ها تشخیص داده می‌شوند تحت مکمل بسته‌اند. II) فرض کنیم D یک DFA باشد و C = L(D). در این صورت یک DFA دیگر مانند D̄ وجود دارد که زبان مکمل L(D)…

گرامر G با قوانین زیر را در نظر بگیرید که در آن S متغیر شروع است: S → 0S0 0S1 1S0 1S1 0 کدام رشته در زبان این گرامر قرار ندارد؟

فرض کنید: L_1 = a^n w w^R a^n : n ≥ 0, w ∈ ∘, ! ^ L_2 = a^n b^j a^n b^j : n, j ≥ 0 کدام‌یک در مورد این دو زبان درست است؟

فرض کنیم M یک DFA برای زبان زیر باشد: ‏ L = w ∈ a,b ^() : ‏ w با b شروع می‌شود با b تمام می‌شود و تعداد فردی a دارد M حداقل چند حالت دارد؟

فرض کنیم L زبان عبارت منظم زیر باشد: R = (۰+۱)^() ∘ ((۰+۱)(۰+۱)(۰+۱))^() ∘ (۰+۱)^() به‌ازای کدام مقدار برای x عبارت w = ۰۱۰۱۱۱۱x۰ در L قرار می‌گیرد؟

فرض کنیم Q یک اتوماتای شبیه به PDA باشد با این تفاوت که به جای پشته مجهز به یک نوار باشد. به عبارت دیگر، Q ماشینی متناهی‌الحالت است که با توجه به نماد ورودی فعلی، حالت فعلی و نماد جلویی نوار حرکت…

گوییم زبان L عضو کلاس C است هرگاه گرامر مستقل از متن برای آن وجود داشته باشد که همهٔ قوانین آن به‌ صورت A → xBy یا A → x باشد که x و y رشته‌های پایانی (احتمالاً تهی) هستند. این گزاره‌ها را در نظر…

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

NFA زیر را در الفبای a = ∑ به DFA معادل تبدیل می‌کنیم DFA حاصل حداقل چند حالت دارد؟ (گراف: حالت شروع S، با گذارهای ε از S به A و از S به E. شاخه بالا: A با a به B، B با a به C، به‌علاوه C با ε به A و…