632 views

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

edited | 632 views

$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 \}$

edited by
0

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?

0
@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
+1
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
+2
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.
0

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

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

correct me if I am wrong
+1

yes, correct

it is accepting 0*1n01n + 0*

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?

0

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