سوالات

فرض کنیم L زبان عبارت منظم r = (۰^۱۰^)(۱۰^۱۰^)^ باشد. با فرض β = (۰۱)^۱۴۰۴ ∘ (۱۰۱)^۱۴۰۵ و α = (۱۰۰)^۱۴۰۴ ، کدام گزینه درست است؟

فرض کنیم L زبان اتوماتای متناهی معیّن (DFA) زیر روی الفبای ۰,۱ باشد. این اتوماتا چهار حالت دارد: حالت آغازین q_0 (پذیرنده) با گذارهای q_0xrightarrow ۰ q_0 و q_0xrightarrow ۱ q_1 ؛ حالت q_1 (پذیرنده)…

فرض کنیم L زبان گرامر زیر با متغیر شروع S باشد: S → ES ε E → aEb ε اگر α = (a^۲b^۲)^۱۴۰۴(a^۳b^۳)^۱۴۰۵ و β = (a^۳b^۳)^۱۴۰۴(a^۲b^۲)^۱۴۰۵ کدام گزینه درست است؟

فرض کنیم L_1 = w a^2k w ∈ a, b ^, w = k و L_2 = a^k w w ∈ a, b ^, w = k . از این دو زبان کدام منظم است؟

فرض کنیم L_1 = a^n b^m : n ≠ 2m و L_2 = a^n b^m : n ≤ m^2 . از این دو زبان کدام مستقل از متن است؟

فرض کنید دو زبان زیر روی الفبای a,b,c تعریف شده باشند: L_1 = w ∈ a,b,c ^ middle n_a(w) + n_b(w) = n_c(w) L_2 = w ∈ a,b,c ^ middle n_a(w) + n_b(w) = 2^(n_c(w)) از این دو زبان کدام مستقل از متن است؟

زبان L_1 روی a,b به‌صورت بازگشتی با دو قانون زیر تعریف می‌شود: الف ـ λ ∈ L_1 ب ـ اگر x ∈ L_1 آنگاه aabx ∈ L_1 و xbb ∈ L_1 . به‌علاوه فقط رشته‌هایی در L_1 هستند که از دو قانون بالایی به‌دست آمده…

(… نماد c جایگزین بالای پشته شود. ) شکل زیر یک ماشین پشته‌ای (PDA) است که زبان L_۱ را می‌پذیرد؛ برچسب هر یال به‌صورت «ورودی، بالای پشته / جایگزین» خوانده می‌شود: حالت شروع q_0 با دو حلقه: a, a/aa و…

ماشین تورینگ زیر براساس الفبای ورودی a, b (با نماد تهی □ و نماد نشانه‌گذاری x ) به‌صورت زیر تعریف شده است (نمودار حالت‌ها): q_0 xrightarrow a → □, R q_1 q_1 xrightarrow a → a, R q_1 ، q_1 xrightarrow…

اگر A متغیر و S متغیر شروع باشد، از دو گرامر زیر کدام‌یک در فرم نرمال چامسکی هستند؟ گرامر «الف»: S → AS a A → SA b گرامر «ب»: S → AS a A → SA aa