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\}$
edited | 138 views

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 .

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.