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

Despite the wording, $G$ is an unrestricted (type-0) grammar — the productions $bB \to bbb\,B$ and $aS_1b \to aa$ rewrite strings, not single nonterminals. Handle the two factors separately: $S_1$ lays down the $a$'s and the first block of $b$'s, while $B$ pumps extra $b$'s.

Step 1 — the $S_1$ factor. From $S \to S_1 B$, applying $S_1 \to aS_1b$ exactly $m$ times gives $S_1 \Rightarrow a^{m}\,S_1\,b^{m}.$ The only way to remove $S_1$ is the context-sensitive rule $aS_1b \to aa$, which needs the surrounding pattern $a\,S_1\,b$, so $m \ge 1$. Replacing the innermost $a\,S_1\,b$ by $aa$: $a^{m} S_1 b^{m}=a^{m-1}(aS_1b)b^{m-1}\;\Rightarrow\;a^{m-1}\,aa\,b^{m-1}=a^{m+1}b^{m-1}.$ With $n:=m\ge 1$ the sentential form is $a^{\,n+1}\,b^{\,n-1}\,B$. So the number of $a$'s is fixed at $n+1$ (hence at least $2$).

Step 2 — the $B$ factor (pumping $b$'s). Now $B$ is preceded by $b^{\,n-1}$. The rule $bB \to bbb\,B$ fires only when a $b$ sits immediately left of $B$, and each firing adds two $b$'s. Applying it $k'$ times ($k'\ge 0$) and finishing with $B\to\varepsilon$: $a^{\,n+1}\,b^{\,n-1}\,B\;\Rightarrow\;a^{\,n+1}\,b^{\,(n-1)+2k'}.$

Step 3 — collect the counts. With $n\ge 1,\ k'\ge 0$ the $b$-count is $(n-1)+2k'\in\{\,n-1,\ n+1,\ n+3,\ n+5,\dots\}.$ Writing it as $n+k$, the surplus $k$ runs over $\{-1,1,3,5,\dots\}$ — odd values starting at $-1$, advancing in steps of $2$. Therefore $L(G)=\{\,a^{\,n+1}b^{\,n+k}\mid n\ge 1,\ k=-1,1,3,5,\dots\,\},$ which is option 1.

Why the others fail.

• Option 4 ($a^{n}b^{m}$, independent counts) over-generates: the $a$- and $b$-counts here are tightly coupled.
• Option 3 ($a^{n+1}b^{n+k},\ k\ge 0$) has the right base coupling but a step of $1$; the grammar shifts the $b$-count only in steps of $2$, so e.g. $a^{n+1}b^{n}$ is never derivable — the parity is wrong.
• Option 2 ($a^{n}b^{n+2k},\ n\ge 2$) forces $\#b\ge\#a$, yet $aa$ (with $0$ $b$'s) is generated, so $\#b$ can be well below $\#a$; it also has the wrong leading $a$-offset.

Exam trick: When the options differ only in the step of the surplus exponent ($k\ge 0$ vs. $k=0,2,4,\dots$ vs. $k=-1,1,3,\dots$), just count how many terminals one application of the pumping rule adds. Here $bB\to bbbB$ appends two $b$'s, forcing a step of $2$ in the exponent — which instantly kills every "step-of-one" ($k\ge 0$) option.