The Gateway to Computer Science Excellence
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 (49.8k points)
edited by | 152 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 (50.8k 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.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

28,946 questions
36,791 answers
34,688 users