retagged by
511 views
2 votes
2 votes

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:

  1. $\{0^n 1^{n} \mid n \geq 0\}$
  2. $\{0^n 1^{2n} \mid n \geq 0\}$
  3. $\{0^{2n} 1^n \mid n \geq  0\}$
  4. $\{0^{2n} 1^{2n} \mid n  \geq  0\}$
retagged by

2 Answers

1 votes
1 votes
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.
0 votes
0 votes

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$

 

Answer:

Related questions

4 votes
4 votes
0 answers
2
Bikram asked Aug 12, 2017
607 views
The number of possible finite automata with two states $a0$ and $a1$ (where $a0$ is always the initial state over the alphabet $\{p, q\}$) which accepts empty language is...
0 votes
0 votes
1 answer
3
Bikram asked Aug 12, 2017
260 views
What is the regular expression corresponding to the above DFA?$(01 + (00)^*1)^*$$0^*10^*$$(10 + 0(00)^* (1 + 01) )^*$$0(00)^*10^*$