in Theory of Computation edited by
6,133 views
30 votes
30 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 edited by
6.1k views

1 Answer

54 votes
54 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

4 Comments

Note : if we add one more transition δ(q1,ϵ,Z0)=(q1,ϵ),  then L will be 

this should be   δ(q1,ϵ,Z0)=(q1,Z0)  As when we get Z0 as the TOS then only it is accepting right?

is anything wrong in this?

0
0

@Pranavpurkar no

Note : if we add one more transition δ(q1,ϵ,Z0)=(q1,ϵ),  then L will be 

This transition is correct.

Initially we have $Z_0$ as top of the stack and to accept a language by empty stack method we have to even remove even $Z_0$ when the input string is over.  

source

0
0

How is this DPDA which is accepting by empty stack able to accept 0* as prefix property won’t be followed then? @Praveen Saini

0
0

Related questions