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

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