The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+15 votes

Let $M=(\{q_0, q_1\}, \{0, 1\}, \{z_0, X\}, \delta, q_0, z_0, \phi)$ be a Pushdown automation where $\delta$ is given by

$\delta(q_0, 1, z_0) = \{(q_0, xz_0)\}$

$\delta(q_0, \epsilon, z_0) = \{(q_0, \epsilon)\}$

$\delta(q_0, 1, X) = \{(q_0, XX)\}$

$\delta(q_1, 1, X) = \{(q_1, \epsilon)\}$

$\delta(q_0, 0, X) = \{(q_1, X)\}$

$\delta(q_0, 0, z_0) = \{(q_0, z_0)\}$z

  1. What is the language accepted by this PDA by empty stack?

  2. Describe informally the working of the PDA

asked in Theory of Computation by Veteran (59.5k points)
edited by | 632 views

1 Answer

+20 votes
Best answer

$q_0$ is start state 

$\mathbf{\delta(q_0,0,Z_0) = (q_0,Z_0)}$  

[ Do Nothing operation, just read any no of $0$'s but do not keep in stack (any no of $0$'s because on reading $0$'s it remains on same state $q_0$) ]

$\mathbf{\delta(q_0,1,Z_0) = (q_0,XZ_0)}$  [ Read first $1$ and keep one $X$ in stack ]

$\mathbf{\delta(q_0,1,X) = (q_0,XX)}$  [Read any no of $1$'s and keep one $X$ for each $1$ in stack ]

$\mathbf{\delta(q_0,0,X) = (q_1,X)}$  

[ Read single $0$ and do nothing in stack, state changed from $q_0$ to $q_1$ ]

$\mathbf{\delta(q_1,1,X) = (q_1,\epsilon)}$  

[ Pop out one $X$ from stack on reading  each $1$ on state $q_1$ (matching each $1$ with the $1$ read before single $0$ ) ]

$\mathbf{\delta(q_0,\epsilon,Z_0) = (q_0,\epsilon)}$  

[stack is empty , inputs are accepted here ,that is , $\epsilon$ or any of $0$'s (we read earlier with Do Nothing operation) ]

$\mathbf{L = \{ 0^m , m \geq 0 \}}$

No input accept after reaching on $q_1$ because stack will remain with $Z_0$, stack initial symbol

Note : if we add one more transition $\mathbf{\delta(q_1,\epsilon,Z_0) = (q_1,\epsilon)}$ , then $L$ will be $\{ 0^m \bigcup 0^i1^j01^j ,m,i,j \geq 0 \}$

answered by Veteran (55k points)
edited by

Sir, but if 0i1j01^k where k<j then stack will not become empty but since accepting state has reached then can we say the string is accepted?

@gateaspirant1  how can u reach to the  accepting state  take this  0^21^501^3 and analyze plz ur doubt will be clear  otherwise i did not get u
if q1 were the accepting state then it would have  been  accepted.. but in this PDA no accepting state is there so only acceptance is possible by emptiyng stack .. When I wrote the comment , cz I saw somewhere q1 as accepting state
Great Question and Superb Ans.

Note:- This PDA follows Empty stack mechanism not Final state(q1 is not final state here)

the language will accept only when stack is empty and here stack is getting empty only in q0.

@Rajesh Pradhan, here, there is no final/accepting state right? then how will any language be accepted?

^ Pda will accept the language when string is over and stack is empty.
Strings like 101, 11011, 1110111.. are also accepted here

correct me if I am wrong

yes, correct

it is accepting 0*1n01n + 0*


@joshi_nitish @Rajesh Pradhan Can you please draw the PDA, how it will look like?

@just_bhavana Ma'am may you also give your opinion on this like how strings like 101, 11011, 1110111.. are also accepted here?


Yes. I also got that is accepting 0*1n01n + 0* with 3 states in the PDA.

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

37,996 questions
45,492 answers
48,591 users