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

The language $L=\{a^{2^{n}}\}$ contains the strings $a,\;aa,\;aaaa,\;aaaaaaaa,\dots$ of length $1,2,4,8,\dots$ Since $\{a^{2^{n}}\}$ is not context-free, $G$ must use context (left- and right-hand context symbols), and the answer hinges on two independent decisions.

1. What goes in place of $?$

The symbols $[$ and $]$ are end-markers; $R$ sweeps right doubling each $a$ ($Ra\to aaR$), turns around at the right end ($R\to L]$), and $L$ sweeps left ($aL\to La$) back to the start marker, where $[L\to[R$ launches another doubling pass. Each full round trip doubles the number of $a$'s, giving exactly $a^{2^{n}}$.

To stop, the sweeping head becomes a terminating marker: $R\to H$. This $H$ must now travel all the way left to the start marker $[$ and disappear. The only rule that consumes $H$ is the final $[{?}\to\varepsilon$, so $H$ has to reach $[$. The rule $aH \to {?}\,a$ must therefore move $H$ one cell to the left, i.e. turn $aH$ into $Ha$. That forces $? = H \qquad\Longrightarrow\qquad aH\to Ha,\qquad [\,H\to\varepsilon .$ No other choice lets $H$ migrate to the start marker, so $? = H$. This eliminates options 1 ($R$), 2 ($[R$) and 4 ($aH$).

2. The Chomsky type of $G$

A grammar is context-sensitive (Type 1) only if it is non-contracting: every production $\alpha\to\beta$ satisfies $|\alpha|\le|\beta|$ (the lone exception $S\to\varepsilon$ is allowed when $S$ never appears on a right-hand side). Check the productions:

The clean-up rule $[\,H\to\varepsilon$ erases a length-2 left side, so it is contracting. Because this is not an $S\to\varepsilon$ production, $G$ violates the Type-1 length condition. Hence $G$ is Type 0 (unrestricted), not context-sensitive. This rules out options 2 and 4 (which claim Type 1).

Conclusion

Type 0 (unrestricted) and $? = H$ — option 3.

Pitfall: $L=\{a^{2^n}\}$ is a context-sensitive language (a non-contracting grammar exists), but the grammar as written contains the erasing rule $[\,H\to\varepsilon$, so this particular grammar is Type 0. The question asks about the type of this grammar, not the inherent class of the language.