edited by
5,461 views
2 votes
2 votes

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 by

2 Answers

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

0 votes
0 votes
 
 
 
 

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

Related questions

0 votes
0 votes
1 answer
2
Abhisek Tiwari 4 asked Nov 6, 2018
703 views
Consider Ldf set all languages accepted by DPDA by final state,Lef set of all languages accepted by DPDA by Empty stack ThenA)Ldf proper subset of Lef.B)Ldf = Lef.C)Lef ...
0 votes
0 votes
0 answers
3
Na462 asked Sep 9, 2018
606 views
Consider following PDA WHICH OF FOLLOWING IS TRUE ABOUT LANGUAGE ACCEPTED BY IT ?A. Regular but infiniteB. Regular but finiteC. DCFL but not regularD. CFL but not DCFL
0 votes
0 votes
0 answers
4
Na462 asked Sep 5, 2018
960 views
Consider A given PDA as following Qo is the start state here. What is the language accepted by the given PDA ?1. { ( bn a bn a )m | m,n ≥ 0 }2. { ( bn a bn a )m | m,n ...