The Gateway to Computer Science Excellence
+53 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$
in Theory of Computation by Boss (30.8k points)
edited by | 8.1k views
@Arjun Sir ,@Anirudh  I understood the ans. But I have a basic doubt regarding the question

According to Wikipedia for PDA
\,\delta is the transition function, mapping Q\times (\Sigma \cup \{\varepsilon \})\times \Gamma into finite subsets of Q\times \Gamma ^{*}
 where \,\Gamma is a finite set which is called the stack alphabet  .

My question is ... How in place of \,\Gamma  which should be a single letter from stack alphabet whole Z is possible .(In ans we considered ...Z is used to represent the entire stack content except the top )

That basically means the 'single letter' which is given in PDA definition must come to the left of 'Z' in the given question and wherver it is not, that denotes $\epsilon$.
@Arjun Sir means when we r writing (qi,a,a)=(qj,aa) this is same as (qi,a, aZ)=(qj,aaZ) is it sir?
@Rajesh Yes
Not getting  help me
But how we understand that Z is entire string on stack is mentioned nowhere in question
Exactly my question. There's no mention in the question that Z being the entire string without the top.

3 Answers

+94 votes
Best answer

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 '$1$', a '$1$' is pushed and for a '$0$' a '$0$' is pushed. In $q_1$ state, for a '$0$' a '$1$' is popped and for a '$1$' a '$0$' 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.

by Veteran (431k points)
edited by
Sir I atill did't got that. Is Top to bottom reading implies Z will always be  on the  top so that we can push the input ??? I think  even though in top to bottom the last input will be at the top.

I may have misinterpreted you.

PLease elaborate .
this is a gate 2015 question. how has it been answered in feb 2014?
[Month][Date][Year if older than 1 year]
Sir , If input is 0 and TOS is 1 , or if input is 1 and TOS is 0 and we are in state q0 , then where do we make the transition since q0 moves to q1 only when it sees that input is 0 and TOS is 1
no. You are seeing the transition wrong- in State q0, TOS is not considered. You can see again- only in q2, we look at TOS.
Plz clear the transition from q0 to q1..... i m not getting it....
I think now u got it
sir... wht this question  is asking m not getting plz explain ??
In simple words PDA is saying I will accept string if the second half of the string represents complement of the first half in reverse order.
@Arjun sir , I have one small extension to the question.

Consider this transition in the given diagram .

0/1/ϵ ,Z--->Z .     This transition  ϵ ,Z--->Z  says that  without reading any input symbol  we can make a transition  from q0 to q1.

By the way , we are not using  this transition  while evaluating the strings given in this question since all the strings are odd length strings. This transition can be used for accepting even length strings of the same pattern like 0101.

Am I correct sir ?

Or is there any specific purpose for this transition  ϵ ,Z--->Z  ?
its purpose is to accept even palindromes

Irrespective of what is on the top of stack. whether input is 1 or 0, it is pushed on to the stack. So how the system goes from q0 to q1? Please explain this transition
@ balaeinstein
if 0/1/ϵ ,Z--->Z  transition becomes  ϵ ,Z--->Z ,
then, then last 0 cannot be removed before pop operation started
means 101100 after pop will be 110010 and not 10010

@srestha actually 0/1/ϵ ,Z--->Z  can simply be replaced by   ϵ ,Z--->Z  . There is no change in the functionality of PDA . The NPDA can be generalized for both odd and even length strings . 

Please see the image from Ullman . This NPDA  is for recognizing  the strings of the form  ww^r. 


See I donot think , this picture transition is same as the question shows

According to the question transition of q0 to q1 would be

$\epsilon ,z_{0}/z_{0},$

$0 ,z_{0}/z_{0},$

$1 ,z_{0}/z_{0}$

otherwise,why the input is of 6 digits and output 5 digits?

@srestha  examine the transitions carefully . In the question, Z  represents the entire content of the stack . But in the diagram they have represented transitions for every input symbol .The transitions from q0 to q1 in the diagram can simply be replaced by  ϵ ,Z--->Z  as  per the notation of the gate question where Z represents the entire content of the stack . But In the diagram they have used ϵ  transitions for every possible input symbol.

you simply derive, why the input is of 6 digits and output 5 digits?

See in transition of q1 $0,1z\rightarrow z$

where for same transition from q0 to q1 $0z\rightarrow z$

they are not same right?

@srestha can u explain a bit what for transition from q0 to q1 is?
plz tell me what r u getting?
ok now i got it need of further explanation Thanku!
+30 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.
by (139 points)

This is exactly the solution I was looking for.

But is there any way to decide the following move ?

6. state q0. i/p 0. do nothing. move to q1.

Asking because nothing is clearly mentioned.

you have to reach final state to accept the string, so this could be only possible. Suppose after 3 transaction in q0 you move to q1 and 1 is on the top of stack and in q1 you can make only one transaction and then you will be in dead situation that upcoming input is 0 and top of the stack is 0 so, you can't make any move.
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
+9 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

by Veteran (63k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,292 answers
104,916 users