GATE CS 2016 Set 1 Q.53 (CS Q.43): Context-Free Grammars, Pushdown Automata and CFLs

Consider the transition diagram of a PDA given below with input alphabet $\Sigma = \{a, b\}$ and stack alphabet $\Gamma = \{X, Z\}$ . $Z$ is the initial stack symbol. Let $L$ denote the language accepted by the PDA.

State transition diagram of a pushdown automaton with input alphabet {a, b} and stack alphabet {X, Z}, where Z is the initial stack symbol. The start state q0 is an accept state (double circle) with a self-loop labeled 'a, X/XX' and 'a, Z/XZ'. A transition from q0 to q1 is labeled 'b, X/epsilon'. State q1 has a self-loop labeled 'b, X/epsilon' and transitions to accept state q2 (double circle) on 'epsilon, Z/Z'. — PDA transition diagram

Which one of the following is TRUE?

$L = \{a^n b^n \mid n \ge 0\}$ and is not accepted by any finite automata

$L = \{a^n \mid n \ge 0\} \cup \{a^n b^n \mid n \ge 0\}$ and is not accepted by any deterministic PDA

$L$ is not accepted by any Turing machine that halts on every input

$L = \{a^n \mid n \ge 0\} \cup \{a^n b^n \mid n \ge 0\}$ and is deterministic context-free

Official answer and solution

Official answer: D
From: Official GATE 2016 answer key

Solution

Trace the behavior of the PDA on inputs to determine the accepted language and verify whether the transition relation satisfies determinism.

Examine the transitions of the PDA:

Initial state is $q_0$ with stack bottom marker $Z$ . State $q_0$ is an accepting state (double circle).
On input $a$ in state $q_0$ : $(q_0, a, Z) \to (q_0, XZ)$ and $(q_0, a, X) \to (q_0, XX)$ . Each $a$ pushes an $X$ onto the stack.
Since $q_0$ is an accepting state, any sequence of $a$ 's alone is accepted by entering no further transitions. Thus, $\{a^n \mid n \ge 0\} \subseteq L$ .

Transitions involving $b$ :

From $q_0$ , on input $b$ with $X$ on top: $(q_0, b, X) \to (q_1, \varepsilon)$ , popping one $X$ .
In state $q_1$ , on input $b$ with $X$ on top: $(q_1, b, X) \to (q_1, \varepsilon)$ , popping one $X$ for each $b$ .
From $q_1$ , on $\varepsilon$ with $Z$ on top: $(q_1, \varepsilon, Z) \to (q_2, Z)$ , reaching accepting state $q_2$ .
State $q_2$ has no outgoing transitions. It is reached if and only if the number of $b$ 's matches the number of $a$ 's that were pushed on the stack ( $n$ occurrences of $a$ followed by $n$ occurrences of $b$ ).
Therefore, strings of the form $a^n b^n$ for $n \ge 1$ (and $n=0$ at $q_0$ ) are accepted.

Total accepted language:

L = \{a^n \mid n \ge 0\} \cup \{a^n b^n \mid n \ge 0\}

Checking for determinism (DPDA):

In state $q_0$ : transitions are defined for $(a, Z)$ , $(a, X)$ , and $(b, X)$ . There are no $\varepsilon$ -transitions from $q_0$ , and each input/stack combination has at most one choice.
In state $q_1$ : transition on input $b$ requires stack top $X$ , while the $\varepsilon$ -transition requires stack top $Z$ . Because the stack symbols $X$ and $Z$ are disjoint, there is never a choice between reading an input symbol and taking an $\varepsilon$ -move.
In state $q_2$ : no transitions exist.
Since every configuration has at most one valid move, the PDA is deterministic. Hence, $L$ is a deterministic context-free language (DCFL).

Final answer

Common trap

Assuming that having an epsilon transition from $q_1$ makes the PDA non-deterministic, ignoring that the epsilon transition requires stack symbol $Z$ while the $b$ -loop requires stack symbol $X$ .

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2016 Computer Science and Information Technology (CS) Session 1
Question: 53 of 65, printed as CS Q.43
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source