دو زبان 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 از این دو زبان، کدام مستقل از متن است؟

سوال ۸۷ کنکور ارشد علوم کامپیوتر ۱۴۰۳

اهمیت

۰/۵

دو زبان $L_1$ و $L_2$ را بر $\Sigma = \{a, b\}$ به‌صورت زیر در نظر می‌گیریم:

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

$L_2 = \{a^n b^j : 0 \leq n \leq j^2\}$

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

#context-free#pumping-lemma#non-cfl#cross-serial-dependency#formal-languages