Ullman (TOC) Edition 3 Exercise 6.4 Question 1 (Page No. 256)

Question

For each of the following PDA's, tell whether or not it is deterministic. Either show that it meets the definition of a DPDA or find a rule or rules that violate it.

$a)$

 

$b)$

Suppose the $PDA, $    $P=(\{q,p\},\{0,1\},\{Z_{0},X\},\delta,q,Z_{0}.\{p\})$ has the following transition function$:$

1. $\delta(q,0,Z_{0})=\{(q,XZ_{0})\}$
2. $\delta(q,0,X)=\{(q,XX)\}$
3. $\delta(q,1,X)=\{(q,X)\}$
4. $\delta(q,\in,X)=\{p,\in\}$
5. $\delta(p,\in,X)=\{p,\in\}$
6. $\delta(p,1,X)=\{(p,XX)\}$
7. $\delta(p,1,Z_{0})=\{p,\in\}$

 

$c)$

Convert the $PDA$  $P=(\{p,q\},\{0,1\},\{X,Z_{0}\},\delta.q.Z_{0})$ to a $CFG,$ if $\delta$ is given by $:$

1. $\delta(q,1,Z_{0})=\{(q,XZ_{0})\}$
2. $\delta(q,1,X)=\{(q,XX)\}$
3. $\delta(q,0,X)=\{(p,X)\}$
4. $\delta(q,\in,X)=\{(q,\in)\}$
5. $\delta(p,1,X)=\{(p,\in)\}$
6. $\delta(p,0,Z_{0})=\{(q,Z_{0})\}$