edited by
23,489 views
83 votes
83 votes

Consider the NPDA $$ \left \langle Q= \left \{ q_{0}, q_{1}, q_{2} \right \},\Sigma = \left \{ 0, 1 \right \}, \Gamma = \left \{ 0, 1, \perp  \right \}, \delta, q_{0}, \perp, F =\left \{ q_{2} \right \} \right \rangle $$, where (as per usual convention) $Q$ is the set of states, $\Sigma$ is the input alphabet, $\Gamma $ is the stack alphabet, $\delta $ is the state transition function $q_{0}$ is the initial state, $\perp $ is the initial stack symbol, and $F$ is the set of accepting states. The state transition is as follows:

Which one of the following sequences must follow the string $101100$ so that the overall string is accepted by the automaton?

  1. $10110$
  2. $10010$
  3. $01010$
  4. $01001$
edited by

4 Answers

Best answer
143 votes
143 votes

Here, $Z$ is used to represent the entire stack content except the $top$
$Z$ is the string in Stack read from top to bottom. $1, Z \to 1Z$ means, on input symbol $1$, the stack content changes from $Z$ to $1Z$

In $q_0$ state, for $\text{‘}1\text{’},$ a $\text{‘}1\text{’}$ is pushed and for a $\text{‘}0\text{’}$ a $\text{‘}0\text{’}$ is pushed. In $q_1$ state, for a $\text{‘}0\text{’}$ a $\text{‘}1\text{’}$ is popped and for a $\text{‘}1\text{’}$ a $\text{‘}0\text{’}$ is popped. So, the given PDA is accepting all strings of of the form $x0x_r'$ or $x1x_r'$ or $xx_r'$, where $x_r'$ is the reverse of the $1$'s complement of $x$. i.e.:

The given string $101100$ has $6$ letters and we are given $5$ letter strings. So, $x0$ is done, with $x = 10110$. So, $x_r' = (01001)_r = 10010$. 

Answer is option B.

edited by
52 votes
52 votes

these are the transitions which occur when we add option B,

10 110 0 10 010

  1. state q0. i/p 1. push 1. remain in q0.
  2. state q0. i/p 0. push 0 remain in q0.
  3. state q0. i/p 1. push 1. remain in q0.
  4. state q0. i/p 1. push 1. remain in q0.
  5. state q0. i/p 0. push 0. remain in q0.
  6. state q0. i/p 0. do nothing. move to q1.
  7. state q1. i/p 1. top of the stack 0. pop. remain in q1.
  8. state q1. i/p 0. top of the stack 1. pop. remain in q1.
  9. state q1. i/p 0. top of the stack 1. pop. remain in q1.
  10. state q1. i/p 1. top of the stack 0. pop. remain in q1.
  11. state q1. i/p 0. top of the stack 1. pop. remain in q1.
  12. state q1. i/p epsilon. top of stack tau. move to accept state.
12 votes
12 votes

Quetion is asking about what is added to 101100.X  so that whole string is accepted  .. so what is the value of x.

now put one by one option. string is acceptes in form of wwr and w x wr

1 votes
1 votes

First of all read the question carefully, 
They are asking 
$\text{Which sequence}$ $\color{Red}\text{must follow the string 101100}$ $\text{so that the overall string is accepted by the automaton?}$

So, from here we can assume overall string will be like $101100\;something$ So we put all options – 

  1. $10110$
    overall string: $101100\color{Red}10110$
    operation sequence: $(1:push)(0:push)(1:push)(1:push)(0:push)(0:go\;q1)(1:pop \;0)(0:pop\;1)(1: {\color{Magenta}oops !})$ 
    Problem !! at $1$ we should have $0$ at top of stack to pop but we have $1$. So this string will not be accepted.
  1. $10010$
    overall string: $101100\color{Red}10010$
    operation sequence:$(1:push)(0:push)(1:push)(1:push)(0:push)(0:go\;q1)(1:pop\;0)(0:pop\;1)(0:pop\;1)(1:pop\;0)(0:pop\;1)$
    So, the stack is now empty. And we can go to $q2$ and accept the string.
  2. $01010$
    overall string: $101100\color{Red}01010$
    operation sequence: $(1:push)(0:push)(1:push)(1:push)(0:push)(0:go\;q1)(0: {\color{Magenta}oops!})$
    Problem !! here we should have have $1$ at top of stack to pop but we have $0$ at TOS. So, this string not accepted.
  3. $01001$
    overall string: $101100\color{Red}01001$
    operation sequence: $(1:push)(0:push)(1:push)(1:push)(0:push)(0:go\;q1)(0: {\color{Magenta}oops!})$
    Reason similar as C. 

$Ans: B$ 

Answer:

Related questions

80 votes
80 votes
7 answers
2
makhdoom ghaya asked Feb 13, 2015
28,737 views
The least number of temporary variables required to create a three-address code in static single assignment form for the expression $q + r / 3 + s - t * 5 + u * v/w$ is_...
32 votes
32 votes
9 answers
3
makhdoom ghaya asked Feb 13, 2015
24,371 views
Let G be a connected planar graph with 10 vertices. If the number of edges on each face is three, then the number of edges in G is_______________.