The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+2 votes
152 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\}$
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 ....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.


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
91,048 comments
34,688 users