The Gateway to Computer Science Excellence
+22 votes
1.6k views

A push down automation (pda) is given in the following extended notation of finite state diagram:

The nodes denote the states while the edges denote the moves of the pda. The edge labels are of the form $d$, $s/s'$ where $d$ is the input symbol read and $s, s'$ are the stack contents before and after the move. For example the edge labeled $1, s/1.s$ denotes the move from state $q_0$ to $q_0$ in which the input symbol $1$ is read and pushed to the stack.

  1. Introduce two edges with appropriate labels in the above diagram so that the resulting pda accepts the language $\left\{x2x^{R} \mid x \in \left\{0,1\right\}^*,x^{R} \text{ denotes reverse of x}\right\}$, by empty stack.
  2. Describe a non-deterministic pda with three states in the above notation that accept the language $\left\{0^{n}1^{m} \mid n \leq m \leq 2n\right\}$ by empty stack
in Theory of Computation by Veteran (52.2k points)
edited by | 1.6k views

3 Answers

+18 votes

In a) $x2x^R$  

Say for some word $0112110$ we have to push every thing into the stack till $2$ . then we get $1$ then $1$ will be at top of stack so pop it or if get $0$ then $0$ will at top of stack so pop it. For any word of language it is applicable. $2$ is a mark that tell now we have to pop $0$ for $0$ and $1$ for $1$.

So, on the edge $q_0$ to $q_0$ add $0,s/0.s$

and on edge $q_1$ to $q_1$ add $0,0.s/s$

by Veteran (56.8k points)
edited by
+3
sir, here in 0,s/0.s..

's' is not any symbol, it means anything that is on top of stack, no matter what is it???...beacuse if it is not so we require more transitions..
0
@praveen sir ,pls verify once s is content of stack or only stack symbol
0
nitish is right.
+1
In the diagram of a PDA which accepts by empty stack, there's no accept state, right?
+2
@shraddha there should be one more transition on q2, eps| stackSymbol| eps, but seems it's some hypothetical PDA and they don't have any stack symbol at the bottom of the stack. so once input is a member of the language and when input is finished stack will be empty.
+14 votes

part(b) e is epsilon(to denote pop operation)

(q0,0,z0)   |---- (q0,0z0) or (q0,00z0)

(q0,0,0)    |---- (q0,00) or (q0,0000)

(q0,1,0)   |---- (q1,e)

(q1,1,0)   |---- (q1,e)

by Active (1.5k points)
edited by
+1

i dont think it is maintainning nm2n this...

+3
The no. of 0's in stack is between no. of 0's in string and its double (all possible due to non-determinism). Now, the string is accepted if the no. of 1's in string matches the no. of 0's on stack.

@saurav you have to remove the last 2 transitions. Otherwise strings like 00001 will be accepted.
0
right sir 00001 accepted which should'nt but if i remove last 2 transition then how can i maintain empty stack property?
+6
String will be accepted if stack is empty- not otherwise. You don't have to do anything. Non-determinism will take care of it..
0
can we do it like this: for each 0 push two zeroes.When a 1 comes pop 2 0s.If stack becomes empty and there are still 1 left keep on reading it or in other words do nothing just read them till input gets over.Or if $ is reached and top of stack is s then also accept it.
0
in the solution why the same state q0 is maintained in both the transitions??
0

@Arjun sir. I have a doubt here.

 δ(q1,∊, z0)   |---- (q1,∊) . This transition is required, right?  otherwise, how stack top symbol will be popped? And if it is not popped then how stack will be emptied?

0
How it i is maintaining n ≤ m ≤ 2n this ...
0

@Puja,

It is maintaining n ≤ m ≤ 2n by using the 2nd choices for the first 2 IDs (in Bold)- 

(q0,0,z0)   |---- (q0,0z0) or (q0,00z0)

(q0,0,0)    |---- (q0,00) or (q0,0000)

They have been used to bound the n values to a maximum of 2n, using the non-determinism as asked in the question.

It should also have  δ(q1,∊, z0)   |---- (q1,∊) for the 2nd state for empty stack acceptance.

+3
I think the second transition must be of the form

$\delta(q_0,0,0)=\{(q_0,00),(q_0,000)\}$ instead of $\delta(q_0,0,0)=\{(q_0,00),(q_0,0000)\}$
0

@Arjun

Sir , I think this answer needs review this accepts string 00000011 which it should not be

0

@saurav04

What ayush said is true...

Transition in the answer is pushing 3 0's onto stack while we should be pushing only 2 0's.

Your answer would've been correct if they have asked for n<=m<=3n..

Please check it

 

 

 

0

Just drawing what's written in answer by  @@saurav04 sir.

+10 votes

a)

b)

$\lambda$ in the stack part is used to indicate "whatever be the input". And the additional $(\lambda,Z,\lambda)$ was added to pop the initial symbol from the stack.

by Loyal (5.4k points)
edited by
0
What software did you use to construct this?
+1
This is mentioned in Peter Linz's book: http://www.jflap.org/

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,647 questions
56,479 answers
195,421 comments
100,555 users