GATE IT 2006 | Question: 31

Question

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

• A. $\{a^nb^nc^n \mid n ≥ 0\}$
• B. $\{a^lb^mc^n \mid l ≠ m \text{ or } m ≠ n\}$
• C. $\{a^nb^n \mid n ≥ 0\}$
• D. $\{a^mb^n \mid m, n ≥ 0\}$

Comments

DCFL U DCFL != DCFL may or may not when specific language given we cannot use this statement it may lead to wrong conclusion.

---

@Shaik Masthan sir please elaborate more option B (in the context of stack operation)

Thanks 

 

---

Option B option is correct

becz it has two option for accepting same string

 

Answer 1

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 

Comments

how a*b* is regular?it is non regular.

---

@Amlan Kumar Majumdar By Kleen’s theorem, “For every Regular Expression corresponding to the language, a Finite Automata can be generated.” And it is a 2-way theorem, i.e. even the converse is true.

Now when you can write the regular expression as $a^*b^*$ then definitely it is a regular language and is accepted by an FA.

---

If L!=M and M!=N makes it csl and L!=M or M!=N makes it makes CFL !!!

Because of pda having single stack 

Answer 2

Option B.

At a time, the PDA can compare   or,  , 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

Comments

when will be the case when it will accept??

can you write some more implementation detail??

---

It will accept a^l b^m c^n

l not eq m  

Union

a^l b^m c^n

m not eq n

Answer 3

 

1. ) First One is  standard CSL   

with the help of @ praveen Saini sir’s transition states made this  PDA  for  Language b and checking its accepting  memeber of language or not .

100.  a^n b^n n>=0 So can make DPDA    and for  D is regular only  so can make DPDA 

Answer 4

Option A: $ \{ a^n b^n c^n \mid n \geq 0 \} $

This language is not context-free.  Proof via pumping lemma:

 Assume it is CFL. Let $ p $ be pumping length. Choose $ s = a^p b^p c^p $. Any decomposition $ s = uvxyz $ with $ |vxy| \leq p $, $ |vy| \geq 1 $ will fail when pumped  e.g., if $ vxy $ lies in $ a^p $, pumping up increases $ a $’s only → breaks balance. Similarly for other cases.  

• Not CFL → not accepted by any PDA (deterministic or not).  
• Eliminate A.

 

Option B: $ \{ a^l b^m c^n \mid l \ne m \text{ or } m \ne n \} $

This is the complement of $ \{ a^l b^m c^n \mid l = m = n \} $, which is not CFL. But complement of non-CFL may or may not be CFL.

This language can be written as:
$$
\overline{ \{ a^n b^n c^n \mid n \geq 0 \} } \cap \{ a^* b^* c^* \}
$$

But more directly: note that this language includes all strings in $ a^* b^* c^* $ except those where $ l = m = n $. Since the set of strings with $ l = m = n $ is not CFL, and CFLs are not closed under complement. But the language can be expressed as
$$
L = L_1 \cup L_2
$$
where  

• $ L_1 = \{ a^l b^m c^n \mid l \ne m \} $  
• $ L_2 = \{ a^l b^m c^n \mid m \ne n \} $

Each of these is context-free. For $ L_1 $: use a PDA that guesses whether $ l > m $ or $ l < m $, then checks accordingly. Similarly for $ L_2 $. Since CFLs are closed under union, $ L $ is CFL.

It is not deterministic because to check $ l \ne m $, you must guess whether $ l > m $ or $ l < m $, which requires non-determinism. Similarly for $ m \ne n $. There is no way for a DPDA to decide deterministically which inequality holds without backtracking.  It is not a DCFL.

Option C: $ \{ a^n b^n \mid n \geq 0 \} $

This is the classic example of a DCFL.  

• A DPDA can:
• Push $ a $’s onto stack,
• Pop one $ a $ for each $ b $,
• Accept if stack empty at end.

No guessing needed → DCFL.So it is accepted by a DPDA → does not satisfy “NOT by a DPDA”.

 

Option D: $ \{ a^m b^n \mid m, n \geq 0 \} $

This is $ a^* b^* $, which is regular, hence certainly DCFL (in fact, even accepted by a DFA).

 

$$
\color{lime} \boxed{\text{Answer:B}}
$$