push down automata

Question

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

• A. $L=\{a^nb^m \mid n,m \geq 0\}$
• B. $L=\{a^nb^n \mid n \geq 0\}$
• C. $L=\{a^nb^m \mid n,m > 0\}$
• D. $L=\{a^nb^n \mid n > 0\}$

Answer 1

This PDA clearly accepts aⁿ bⁿ  , 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).

Comments

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 Z₀ , 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.

Answer 2

 

 

 

 

This PDA clearly accepts a^nb^n , as its language.

Also there is a production from Q2 to Q0 state that doesn’t read any input and makes stack empty.

So it is PDA where acceptance is by empty stack.

As Acceptance is not by final state, also there are no productions to accept empty string

So, empty strings are not accepted.

Hence , answer D).

Answer 3

This PDA clearly accepts a^nb^n , as its language.

Also there is a production from Q2 to Q0 state that doesn’t read any input and makes stack empty.

So it is PDA where acceptance is by empty stack.

As Acceptance is not by final state, also there are no productions to accept empty string

So, empty strings are not accepted.

Hence , answer D).