edited by
5,044 views
27 votes
27 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
edited by

4 Answers

24 votes
24 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
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
14 votes
14 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
4 votes
4 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

 

 

Related questions