GATE CSE 1998 | Question: 13

Question

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

Answer 1

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

Comments

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*1ⁿ01ⁿ + 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*1ⁿ01ⁿ + 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

Yes.

---

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*1ⁿ01ⁿ

---

Nice solution

---

how $1^{n}01^{n}$ is accepted?

---

@akshita_jain you are not accepting anything when you see 0 so when you see 0’s at the start you remain at qo and when you accept $1^n$ you push X into stack and when you again see 0 you move to state q1 as given in the pda when (but still you didn’t push anything for 0 ) now when you reach q1 you see $1^n$ again and you pop out X for every 1 you see now (as no of 1 is same) so now stack has only symbol zo ,now after reading your string nothing is left to be read so on epsilon we pop zo from stack and hence the stack is empty so we accept it .

---

Can some one explain the Note

---

@Rajesh Pradhan the stack is getting empty in q0 as well as in q1..also

---

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?

---

@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

---

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