in Theory of Computation edited by
3,705 views
25 votes
25 votes

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 edited by
by
2261 2454 2576
3.7k views

1 comment

A Thing to note here  is  s is anything  or like any symbol on the top of the stack so whatever the top of the stack .S represents in that way not any special symbol of the language

 

AND

the transition on qo is    1,s/1.s 

0
0

Subscribe to GO Classes for GATE CSE 2022

4 Answers

23 votes
23 votes

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

edited by
by
212 350 586

5 Comments

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..
4
4
@praveen sir ,pls verify once s is content of stack or only stack symbol
0
0
nitish is right.
0
0
In the diagram of a PDA which accepts by empty stack, there's no accept state, right?
1
1
@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.
3
3
18 votes
18 votes

Part(b)

($ \epsilon$ is used to denote pop operation, $Z$ is the starting symbol on stack)

  • $(q_0,0, Z) \vdash (q_0,0Z)$
  • $(q_0,0, Z) \vdash (q_0,00Z)$
  • $(q_0,0, 0) \vdash(q_0,000)$
  • $(q_0,0,0) \vdash (q_0,00)$
  • $(q_0,1,0) \vdash (q_1,\epsilon)$
  • $(q_1,1,0) \vdash (q_1,\epsilon)$
  • $(q_0,\epsilon, Z) \vdash (q_0,\epsilon)$
  • $(q_1,\epsilon, Z) \vdash (q_1,\epsilon)$
edited by
by
11 25 55

5 Comments

@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

 

 

 

1
1

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

1
1
The question asks for a 3 state PDA so this shouldn't be an acceptable answer isn't it?
1
1

@In that case one can simply add another state q2 from q1 where ∊,z/∊.

0
0
13 votes
13 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.

edited by
by
19 49 85

2 Comments

What software did you use to construct this?
0
0
This is mentioned in Peter Linz's book: http://www.jflap.org/
1
1
2 votes
2 votes

a   

on the state q0 edge from q0 to q0 add 0,s/0.s0,s/0.s
and on state q1 edge from q1 to q1 add 0,0.s/s

 

 

by
1 4

Related questions