The Gateway to Computer Science Excellence
+23 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)\}$

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

  2. Describe informally the working of the PDA

in Theory of Computation by
edited by | 1.4k views

1 Answer

+42 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 \cup 0^i1^j01^j ,m,i,j \geq 0 \}$

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.

what does q0(ϵ,Z0/ϵ) indicates?

what if i had q0(ϵ,X/ϵ) in place of q0(ϵ,Z0/ϵ)?what is its meaning then?

does ths mean if we have X on top of stack,just accept it?

does ϵ here means the end of input string?
@Gate Fever

(q0, €, Z0) = > on q0, with no input and z0 on top of stack (z0 is 'top of stack' symbol)

(q0,€) => Stay on q0 and pop 'top of the stack' and accept the string. (acceptance by empty stack method )

Yes, if you define 'X' as top symbol then this transition also holds good else you will end up accepting wrong inputs

so u mean zo is popped out?

"(q0, €, Z0) = > on q0, with no input and z0 on top of stack (z0 is 'top of stack' symbol) 

(q0,€) => Stay on q0 and pop 'top of the stack' and accept the string"

@Gate Fever

okay:) thanks
@praveen sir , is here q0 state is itself for acceptance by empty stack.

@Praveen sir,

Here the Given PDA is NPDA right,

on $\delta$ (q0,$\epsilon$,zo) = (q0,$\epsilon$)

$\delta$ (q0,1,zo) = (q0,1Z0)

@vasu ...acceptance by empty stack.. stack need to be empty and yes that will happen at q0..

@jatin.. right.

Here as we can see for any number of zero we do not push anything and the stack is empty hence 0* or 0*1n01n

Nice solution
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
52,345 questions
60,484 answers
95,291 users