GATE CSE 2015 Set 1 | Question: 51

Question

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?

• A. $10110$
• B. $10010$
• C. $01010$
• D. $01001$

Comments

Exactly my question. There's no mention in the question that Z being the entire string without the top.

---

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.

2. $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.
3. $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.
4. $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$ 

---

 how we can know here that we have to skip one 0 at the end of $1st part$ if we also push this 0 into stack then option B is also not accepting the whole string ? 

Edit: bcoz in the 1st part there is 6 symbols and in 2nd part there is only 5 symbols and at the end we need to pop  intial stack symbol which means stack should be empty so that we need to skip 1 symbol from 1st part otherwise stack will not be empty at the end for any option

Answer 1

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.

Comments

plz tell me what r u getting?

---

ok now i got it ..no need of further explanation Thanku!

---

I think the meaning of the symbol Z should be specified in the question otherwise it becomes very misleading and ambiguous as different standard books have defined Z differently

Answer 2

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.

Comments

Thanku sooo much..this is what i was looking for

---

i have doubt in 2 line q0 on input 1 and top of stack is z then it will push and remain in q0 only now i/p is 0 then q0 on input 0 if top of stack is 1 then in the given figure there is no state then how it will push and remain in same state

---

osm explanation

Answer 3

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 ww^r and w x w^r. 

Answer 4

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 – 

• A. $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.

• A. $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.
• B. $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.
• C. $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$