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?

- $10110$
- $10010$
- $01010$
- $01001$

0

@Arjun Sir ,@Anirudh I understood the ans. But I have a basic doubt regarding the question

According to Wikipedia for PDA

is thetransition function, mapping into finite subsets of

where is a finite set which is called the stack alphabet .My question is ... How in place of which should be a single letter from stack alphabet whole

Zis possible .(In ans we considered ...Z is used to represent the entire stack content except the top )

+3

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

–1

+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.**

0

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 .

I may have misinterpreted you.

PLease elaborate .

0

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

+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.

+5

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.

0

@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 ?

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 ?

+2

@Arjun

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

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

0

@ 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

rt?

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

rt?

0

@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.

0

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?

0

@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.

+30 votes

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

10 110 0 10 010

- state q0. i/p 1. push 1. remain in q0.
- state q0. i/p 0. push 0 remain in q0.
- state q0. i/p 1. push 1. remain in q0.
- state q0. i/p 1. push 1. remain in q0.
- state q0. i/p 0. push 0. remain in q0.
- state q0. i/p 0. do nothing. move to q1.
- state q1. i/p 1. top of the stack 0. pop. remain in q1.
- state q1. i/p 0. top of the stack 1. pop. remain in q1.
- state q1. i/p 0. top of the stack 1. pop. remain in q1.
- state q1. i/p 1. top of the stack 0. pop. remain in q1.
- state q1. i/p 0. top of the stack 1. pop. remain in q1.
- state q1. i/p epsilon. top of stack tau. move to accept state.

+1

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.

0

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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,292 answers

198,234 comments

104,916 users