سوال ۴۷ کنکور ارشد مهندسی کامپیوتر ۱۴۰۵

Both $L_1$ and $L_2$ demand equal counts across three or more distinct symbols, which is exactly the border between context-free and context-sensitive languages.

Neither is context-free. $L_1=\{1^n2^n3^n\mid n\ge 0\}$ is the textbook language that is not context-free: the CFL pumping lemma fails. For $s=uvwxy$ with $|vwx|\le p$, the block $vwx$ touches at most two of the three symbol groups, so pumping changes at most two counts and breaks the equality $\#1=\#2=\#3$. The identical argument rules out $L_2=\{1^n2^n3^n4^n\mid n\ge 0\}$ (four equal blocks). So option 4 is wrong.

Both are context-sensitive (type 1). Each is generated by a non-contracting grammar (no rule shortens the string), equivalently recognized by a linear-bounded automaton (LBA) whose tape — linear in the input length — can count and compare the blocks. A classic context-sensitive grammar for $L_1$ is:

• $S \to 1\,S\,B\,C \mid 1\,B\,C$
• $C\,B \to B\,C$
• $1\,B \to 1\,2$, $\;2\,B \to 2\,2$, $\;2\,C \to 2\,3$, $\;3\,C \to 3\,3$

(for $n=2$ this derives $112233$). An analogous grammar handles $L_2$.

Chomsky hierarchy.

$\text{regular}\subset\text{context-free}\subset\text{context-sensitive}\subset\text{recursively enumerable (type 0)}.$

Every context-sensitive language is also type 0, so claiming they are "type 0 but not context-sensitive" (option 1) is false; the tightest correct class is context-sensitive. And $L_2$ is context-sensitive exactly like $L_1$, so option 2 fails too.

Hence both $L_1$ and $L_2$ are context-sensitive — option 3.

Exam trick: $a^nb^n$ is context-free, but requiring three or more blocks with equal exponents ($a^nb^nc^n$, $a^nb^nc^nd^n$) pushes the language out of context-free and squarely into context-sensitive.