edited by
17,827 views
32 votes
32 votes

Which of the following languages is accepted by a non-deterministic pushdown automaton (PDA) but NOT by a deterministic PDA?

  1. $\{a^nb^nc^n \mid n ≥ 0\}$
  2. $\{a^lb^mc^n \mid l ≠ m \text{ or } m ≠ n\}$
  3. $\{a^nb^n \mid n ≥ 0\}$
  4. $\{a^mb^n \mid m, n ≥ 0\}$
edited by

3 Answers

Best answer
33 votes
33 votes

Ooption B is correct.

 $L = \{a^lb^mc^n \mid l ≠ m \text{ or } m ≠ n\}$

$(q_0,a,Z_0) \rightarrow (q_0,aZ_0)$

($q_0,a,a) \rightarrow (q_0,aa)$

$(q_0,b,a) \rightarrow (q_1,\epsilon), (q_2,ba) $

[here it is NPDA where we have to check $l\neq m$ or $m\neq n$; for $l\neq m$ we need to pop $a$ for $b$; for $m\neq n$ we need to keep $b$ in stack so that we can pop $b$ for $c$  ]

$(q_1,b,a) \rightarrow (q_1,\epsilon)$

$(q_1,c,a) \rightarrow (q_f,\epsilon)$

$(q_1,b,Z_0) \rightarrow (q_f,\epsilon)$

$(q_2,b,b) \rightarrow q_2,bb)$

$(q_2,c,b) \rightarrow (q_3,\epsilon)$

$(q_3,c,b) \rightarrow (q_3,\epsilon)$

$(q_3,c,a) \rightarrow (q_f,\epsilon)$

$(q3,\epsilon,b) \rightarrow (q_f,\epsilon)$

(A) is wrong as it is not context free

(D)  $a^*b^*$ is regular, so must have DFA , and so an equivalent DPDA

(C) can be accepted using DPDA 

edited by
14 votes
14 votes

Option B.

At a time, the PDA can compare \large a\text{ and }b  or,  \large b\text{ and }c, but not both.

To compare both conditions at the same time, we need a NPDA.

In first case on seeing b pop

2 nd case on seeing b push

Answer:

Related questions

45 votes
45 votes
4 answers
4