The Gateway to Computer Science Excellence
0 votes

The pushdown automata $M=\left \{ \left ( q_{0},q_{1},q_{2} \right ),\left ( a,b \right ) ,\left ( 0,1 \right ),\partial ,q_{0},0,\left \{ q_{0} \right \}\right \}$

$\partial \left ( q_{0},a,0 \right )=\left ( q_{1},10 \right )$

$\partial \left ( q_{1},a,1 \right )=\left ( q_{1},11 \right )$

$\partial \left ( q_{1},b,1 \right )=\left ( q_{2},\lambda \right )$

$\partial \left ( q_{2},b,1 \right )=\left ( q_{2},\lambda \right )$

$\partial \left ( q_{2},\lambda ,0 \right )=\left ( q_{0},\lambda \right )$

Accepts language 

$l=\left \{ a^{n}b^{n}\mid n\geq 0\right \}$

$l=\left \{ a^{n}b^{n}\mid n> 0\right \}$

Please tell me with these two options which one is correct? I think here $q_{2}$ is accepting state , not $q_{0}$ 

As last transition going from $q_{2}$ to $q_{0}$ and not $q_{0}$ to $q_{2}$

Am I right?

in Theory of Computation by Veteran (116k points) | 93 views
This is PDA right, and "Set of Final states" has q0 which is also initial state here, so if only these two options are there we don't need to even check anything as it will accept empty string i.e, a^0b^0. So the answer would definitely be the first one

 "Set of Final states" has q0 


last transition is q2 to q0, and not q0 to q2 

$\left ( Q,\sum,\tau ,\partial ,q_{0},Z_{0},F\right )$

So, here $F=q_{0}$


I thought $q_{2}$ final state

but that is not the case, right?
here goes q2 to q0, so accept the empty state
Yes exactly what I was going to say too😃
thanks a lot

Made Easy diagram showing q2 final :(

So, getting in this trouble

Please log in or register to answer this question.

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
50,666 questions
56,159 answers
93,766 users