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

What the machine does. In $s$ it pushes one a for every input a (loop $a,\varepsilon/a$); an $\varepsilon$-move sends it to $p$. In $p$ each input b either pops an a ($b,a/\varepsilon$) or pushes a b ($b,\varepsilon/b$); an $\varepsilon$-move sends it to $q$. In $q$ each input c pops a b ($c,b/\varepsilon$). Because only $s$ reads a, only $p$ reads b, and only $q$ reads c, every fully-read string has the form $a^{i}b^{j}c^{k}$.

Nondeterminism kills option 3. A PDA is nondeterministic, so a string is in its language iff there exists an accepting path ($\exists$), never “all paths” ($\forall$) — most branches get stuck. “All computation paths reach the final state” is the wrong quantifier. Eliminate option 3.

The empty stack is trivial at the start, so option 4 fails. The stack begins empty, so “at least one path reaches a state with an empty stack” is satisfied by every input (already in $s$, before reading anything), and it never even requires the whole input to be consumed. It characterizes nothing useful. Eliminate option 4.

Final state alone is too weak (option 2). Take the input b, i.e. $a^{0}b^{1}c^{0}$. Path: stay in $s$ (no a) $\to p$; read b via $b,\varepsilon/b$, so the stack becomes b; $\to q$; no c. The whole input is read and the machine sits in the final state $q$ — but the stack still holds a stray b. Under “final state only” this string would be accepted, yet it is not in the intended $L$ (the balance $j=i+k$ fails: $1\ne 0$). So accepting by final state alone over-accepts.

Final state and empty stack is exactly right (option 1). Forcing an empty stack after the entire input is read means every pushed symbol must be cancelled: the $i$ pushed as must be popped by bs in $p$, and the remaining $j-i$ pushed bs must be popped by the $k$ cs in $q$. A valid accepting computation exists iff $i\le j$ and $k=j-i$, i.e. iff $j = i + k,$ which is precisely the intended context-free language $L=\{a^{i}b^{j}c^{k} : j=i+k\}$. The stray-b counterexample is now rejected (non-empty final stack). Hence “reach the final state with an empty stack” is both necessary and sufficient.

Answer: option 1.

Exam trick: PDA acceptance is existential ($\exists$ a good path, not $\forall$), and for the “final state and empty stack” mode the empty-stack test must be applied after the whole input is consumed — not at the start, where every PDA trivially has an empty (or initial) stack.