First time here? Checkout the FAQ!
+2 votes

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






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 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...

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
31,098 users