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

A pushdown automaton (PDA) has a single stack, so it can enforce at most one unbounded count-matching constraint at a time. A language of the form $a^i b^j c^k$ is context-free exactly when the constraint linking the three blocks can be split into nested or sequentially-resolved pairwise matchings (each released before the next is started). Check each option.

Option 1 — $a^t b^t c^{2t}$ (NOT context-free). Here we must simultaneously enforce $\#a = \#b$ and $\#c = 2\,\#a$. Matching $a$'s against $b$'s empties the stack, after which the count $t$ is gone, so the $c$ block cannot be checked. This is the classic $a^n b^n c^n$ pattern (a three-way simultaneous count).

Formally, by the pumping lemma for CFLs, take $z = a^p b^p c^{2p}$ with pumping length $p$. Any decomposition $z = uvwxy$ with $|vwx| \le p$ touches at most two of the three symbol blocks, so pumping ($i = 2$) changes at most two of the three counts and breaks the relation $\#a = \#b = \tfrac{1}{2}\#c$. Hence $L \notin \mathrm{CFL}$.

Option 2 — $a^t b^{t+m} c^m$ (CFL). Split the $b$ block: the first $t$ of them pair with the $a$'s, the last $m$ pair with the $c$'s. Grammar: $S \to A\,B,\quad A \to a\,A\,b \mid a\,b,\quad B \to b\,B\,c \mid b\,c.$ Two independent matchings done in sequence — context-free.

Option 3 — $a^t b^m c^{t+m}$ (CFL). Split the $c$ block: $m$ inner $c$'s match the $b$'s, $t$ outer $c$'s match the $a$'s — a fully nested structure: $S \to a\,S\,c \mid B,\quad B \to b\,B\,c \mid b\,c.$ Context-free.

Option 4 — $a^t b^{t-m} c^m$ with $t > m > 0$ (CFL). Since $t = (t-m) + m$, the $a$ block equals $\#b + \#c$. Split the $a$'s: $m$ outer $a$'s match the $c$'s and $t-m$ inner $a$'s match the $b$'s: $S \to a\,S\,c \mid X\,c,\quad X \to a\,X\,b \mid a\,b.$ Context-free.

Only option 1 forces a genuine three-way simultaneous count, so it is the language that is not context-free.

Exam trick: For an $a^i b^j c^k$ language, ask "can the index constraints be resolved as one nested pair plus one sequential pair (stack pushed then fully popped, then reused)?" If yes it is a CFL; if all three counts must be held at once (as in $a^t b^t c^{2t}$, the $a^n b^n c^n$ family), it is not.