Test by Bikram | Theory of Computation | Test 2 | Question: 24

Question

Consider the following Pushdown Automata Transition Function $\delta$ :

1.  $\delta ( q_0 , \epsilon, z_0 )      =  ( q_0 , \epsilon)$
2.  $\delta ( q_0 , 0, z_0 )     =  ( q_0 , xz_0 )$
3.  $\delta ( q_0 , 0, x )       =  ( q_1 , x)$
4.  $\delta ( q_1 , 0, x )       = ( q_2 , xx)$
5.  $\delta ( q_2 , 0, x )       = ( q_1 , x)$
6.  $\delta ( q_1 , 1, x )       = ( q_1 , \epsilon)$
7.  $\delta ( q_1 , \epsilon, z_0 )     = ( q_1 , \epsilon)$

The language accepted by empty stack is:

• A. $\{0^n 1^{n} \mid n \geq 0\}$
• B. $\{0^n 1^{2n} \mid n \geq 0\}$
• C. $\{0^{2n} 1^n \mid n \geq  0\}$
• D. $\{0^{2n} 1^{2n} \mid n  \geq  0\}$

Comments

@Bikram sir..pls provide the correct solution.

---

I can't understand why option C is not correct.

---

@Bikram Sir Please correct the question

Answer 1

Answer should be B

As for every 0 there are two X's pushed into the stack

And for every 1, one X is popped.

So 011 or 00111 is accepted but 001 or 000011 is not accepted.

Kindly correct it in the Test provided.

Comments

@abbas

it is actually pushing two x's for alternate 0's right?

---

Yes.

Every alternate 0 pushes 2 x's.

Oh... okay .. i got your point. The ques is not right.

---

@abbas

so according to this the answer should be option A

---

For every alternate zero one X pushed up and pop up for every x when 1 encounter here

Answer 2

Answer : $C$ 

But do understand that is not the language of PDA, $C$ is indeed accepted by PDA , but the PDA accepts even more than that. Question only asks for which language will be accepted so the answer is $C$ . 

 

$1.  δ(q_0,ϵ,z_0)=(q_0,ϵ)$

Transition $1$ : The State $Q_0$ can accept empty string . (This transition will not be repeated.)

 

$2.  δ(q_0,0,z_0)=(q_0,xz_0)$

Transition $2$ : Push $x$ for $1^{st}$ $0$ . (This transition will not be repeated.)

Here the first $x$ is added for  $1^{st}$ $0$ but unless it follows by another zero string will be rejected.

 

$3.  δ(q_0,0,x)=(q_1,x)$

Transition $3$ : Do not push $x$ for $2^{nd}$ $0$ and go to state $Q_1$  (This transition will not be repeated.)

$Q_1$ will be state which will accept string later by emptying stack.

 

$4.  δ(q_1,0,x)=(q_2,xx)$

Transition $4$ : Push $x$ for $3^{rd}$ / $odd$,  $0$ and go to state $Q_2$ .

We come to $Q_2$ with odd number of zero hence unless next symbol is zero string will be rejected.

Thus this transition is repeated on every odd number of zero.

$5.  δ(q_2,0,x)=(q_1,x)$

Transition $5$ : Do not push $x$ for $4^{th}$ / $even$,  $0$ and go to state $Q_1$ .

$6.  δ(q_1,1,x)=(q_1,ϵ)$

Transition $6$ : Pop $x$ for every  $1$.

$7.  δ(q_1,ϵ,z_0)=(q_1,ϵ)$

Transition $6$ : If stack is empty when input ends accept the string.

 

Now to sum it up, for every odd number of zero we push one $x$ to stack and go to state corresponding to odd number of zero which is $Q_2$, unless that is $1^{st }$ zero. We allow to pop $x$ for one , only from states which corresponds to even numbers of zero. Which is $Q_1$. 

So for $2n$ number of zeros we can only pop for $n$ number of one. So any string containing even number of zeros, and number of one equal to half of number of zero is accepted. 

With condition that after reading any symbol number of zeros seen before that are always greater than or equal to twice of one that are seen.

Thus PDA accepts all of  $\{ {0^{2n}1^n ∣ n≥0} \}$ strings.

and also the strings like, $000010011$ , $001001001$ , $001000011$

and does not accept stings like  $000011100$ , $001100001$