دو زبان 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$ روی الفبای $\Sigma = \{a, b\}$ را به‌صورت زیر در نظر می‌گیریم:

$L_1 = \{w : n_a(w) = n_b(w)\} \text{ شامل زیررشته‌ی } aab \text{ نیست}$

$L_2 = \{a^n b^j a^i b^n : n, i, j \geq 0\}$

از این دو زبان، کدام مستقل از متن است؟

#context-free#PDA#closure-properties#CFG#regular-intersection