GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
138 views

The pushdown automation $M=(\{q_0, q_1, q_2\}, \{a,b\}, \{0,1\}, \delta, q_0, 0, \{q_0\})$ with

$\delta(q_0,a,0)=\{q_1,10)\}$

$\delta(q_1,a,1)=\{q_1,11)\}$

$\delta(q_0,b,1)=\{q_2,\lambda)\}$

$\delta(q_2,b,1)=\{q_2,\lambda)\}$

$\delta(q_2,\lambda,0)=\{q_0,\lambda)\}$

Accepts the language

  1. $L=\{a^nb^m \mid n,m \geq 0\}$
  2. $L=\{a^nb^n \mid n \geq 0\}$
  3. $L=\{a^nb^m \mid n,m > 0\}$
  4. $L=\{a^nb^n \mid n > 0\}$
asked in Theory of Computation by Veteran (45.1k points)  
edited by | 138 views

1 Answer

+5 votes

This PDA clearly accepts ab , as its language

But as we see that there is a production from Q2 to Q0 makes the input string halt on Q0 , so our final state will be Q0 .

So it will accept empty strings .

Hence , answer B).

answered by Veteran (47.9k points)  

if final state is q2 then what is the meaning of the last line which is delta (q2 ,lemda ,0 ) = (q2 ,lemda)

see what i have made  a conclusion by this line is if you are in state q2 and empty string is the input and 0 is on top of the stck then we are going to get state q0 and halt there .

if this is not the meaning of this line then what exactly you understood by this line ....explain please

@shekhar sir,

u r right,

then there will be Q0 as start and final state..right...?
this is what i am talking about ....here we have a move on empty string

i think 0 in this machine works similar to Z0 , what we generally take as default symbol on stack.

D should be ans... Since there is no epsilon transition on initial state...
δ(q0,b,1)={q2,λ)}δ(q0,b,1)={q2,λ)}

some typo , it should be q1 instead of q0.

@gabbar is right.


Top Users Sep 2017
  1. Habibkhan

    7096 Points

  2. Warrior

    2574 Points

  3. Arjun

    2412 Points

  4. rishu_darkshadow

    2402 Points

  5. A_i_$_h

    2204 Points

  6. nikunj

    1980 Points

  7. manu00x

    1846 Points

  8. makhdoom ghaya

    1760 Points

  9. Bikram

    1744 Points

  10. SiddharthMahapatra

    1718 Points


26,115 questions
33,691 answers
79,843 comments
31,098 users