edited by
6,012 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

edited by

1 Answer

Best answer
54 votes
54 votes

$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

Related questions

29 votes
29 votes
5 answers
1
Arjun asked Oct 17, 2014
8,696 views
Give a regular expression for the set of binary strings where every $0$ is immediately followed by exactly $k$ $1$'s and preceded by at least $k$ $1$’s ($k$ is a fixed...
36 votes
36 votes
2 answers
2
25 votes
25 votes
3 answers
3
Kathleen asked Sep 25, 2014
7,018 views
What is the result of the following program?program side-effect (input, output); var x, result: integer; function f (var x:integer):integer; begin x:x+1;f:=x; end begin x...
42 votes
42 votes
4 answers
4
Kathleen asked Sep 25, 2014
9,977 views
What happens when a bit-string is XORed with itself $n$-times as shown:$\left[B \oplus (B \oplus ( B \oplus (B \dots n \text{ times}\right]$complements when $n$ is evenco...