- Suppose the PDA $P =({\{q,p}\},{\{0,1}\},{\{Z_0,X}\},\delta,q,Z_0,{\{p}\})$ has the following transition function:
- $\delta(q,0,Z_0) = {\{(q,XZ_0)}\}$.
- $\delta(q,0,X) = {\{(q,XX)}\}$.
- $\delta(q,1,X) = {\{(q,X)}\}$.
- $\delta(q,\epsilon,X) = {\{(p,\epsilon)}\}$.
- $\delta(p,\epsilon,X) = {\{(p,\epsilon)}\}$.
- $\delta(p,1,X) = {\{(p,XX)}\}$.
- $\delta(p,1,Z_0) = {\{(p,\epsilon)}\}$.
Starting from the initial ID $(q,w,Z_0)$, show all the reachable ID’s when the input $w$ is:
a) $01$
$ (q,01,Z_0) \vdash (q,1,XZ_0) \vdash (q,\epsilon,XZ_0) \vdash (p,\epsilon,Z_0) $
$(q,01,Z_0) \vdash (q,1,XZ_0) \vdash (p,1,Z_0) \vdash (p, \epsilon, \epsilon) $
b) $0011$
$(q,0011,Z_0) \vdash (q,011,XZ_0) \vdash (q,11,XXZ_0) \vdash (q,1,XXZ_0) \vdash (q,\epsilon,XXZ_0) \vdash (p,\epsilon,XZ_0) \vdash (p,\epsilon,Z_0)$
$(q,0011,Z_0) \vdash (q,011,XZ_0) \vdash (p, 011, Z_0) $
$(q,0011,Z_0) \vdash (q,011,XZ_0) \vdash (q,11,XXZ_0)\vdash (p, 11, XZ_0) \vdash (p, 11, Z_0) \vdash (p, 1, \epsilon) $
$(q,0011,Z_0) \vdash (q,011,XZ_0) \vdash (q,11,XXZ_0)\vdash (p, 11, XZ_0) \vdash (p, 1, XXZ_0) \vdash (p, \epsilon, XXXZ_0) \vdash (p, \epsilon, XXZ_0) \vdash (p, \epsilon, XZ_0) \vdash (p, \epsilon, Z_0) $
$(q,0011,Z_0) \vdash (q,011,XZ_0) \vdash (q,11,XXZ_0) \vdash (q,1,XXZ_0) \vdash (p,1,XZ_0) \vdash (p, 1, Z_0) \vdash (p, \epsilon, \epsilon)$
$(q,0011,Z_0) \vdash (q,011,XZ_0) \vdash (q,11,XXZ_0) \vdash (q,1,XXZ_0) \vdash (p,1,XZ_0) \vdash (p, \epsilon, XXZ_0) \vdash (p, \epsilon, XZ_0) \vdash (p, \epsilon, Z_0)$
c) $010$
$(q,010,Z_0) \vdash (q,10,XZ_0)\vdash (q,0,XZ_0)\vdash (q,\epsilon,XXZ_0)\vdash (p,\epsilon,XZ_0)\vdash (p,\epsilon,Z_0)$
$(q,010,Z_0) \vdash (q,10,XZ_0)\vdash (p, 10, Z_0) \vdash (p, 0, \epsilon)$
$(q,010,Z_0) \vdash (q,10,XZ_0)\vdash (q,0,XZ_0)\vdash (p, 0, Z_0)$
- Design a PDA to accept each of the following languages. You may accept either by final state or by empty stack, whichever is more convenient.
a) The set of all strings of $0$’s and $1$’s such that no prefix has more $1$’s than $0$’s.
PDA $P =({\{q,p}\},{\{0,1}\},{\{Z_0,X}\},\delta,q,Z_0,{\{p}\})$ :
$\delta(q,0,Z_0) = {\{(q,XZ_0)}\}$
$\delta(q,0,X) = {\{(q,XX)}\}$
$\delta(q,1,X) = {\{(q,\epsilon)}\}$
$\delta(q,\epsilon,X) = {\{(p,X)}\}$
$\delta(q,\epsilon,Z_0) = {\{(p,Z_0)}\}$
b) The set of all strings of $0$’s and $1$’s with an equal number of $0$’s and $1$’s.
PDA $P =({\{q,p}\},{\{0,1}\},{\{Z_0,X,Y}\},\delta,q,Z_0,{\{p}\})$:
$\delta(q,0,Z_0) = {\{(q,XZ_0)}\}$
$\delta(q,0,X) = {\{(q,XX)}\}$
$\delta(q,0,Y) = {\{(q,\epsilon)}\}$
$\delta(q,1,Z_0) = {\{(q,YZ_0)}\}$
$\delta(q,1,Y) = {\{(q,YY)}\}$
$\delta(q,1,X) = {\{(q,\epsilon)}\}$
$\delta(q,\epsilon,Z_0) = {\{(p,Z_0)}\}$
- Consider the PDA P from Exercise 1.
a) Convert $P$ to another PDA $P_1$ that accepts by empty stack the same languages that $P$ accepts by final state; i.e., $N(P_1) = L(P)$.
- $P$에서 new start state $s$ 와 erase state $e$ 를 추가한다.
- 아래의 전이 규칙들을 추가한다.
- $\delta(s,\epsilon,X_0) = {\{(q,Z_0X_0)}\}$
- $\delta(p,\epsilon,{\rm any}/\epsilon)=\delta(e,\epsilon,{\rm any}/\epsilon)={\{(e,\epsilon)}\}$
b) Find a PDA $P_2$ such that $L(P_2) = L(P)$; i.e., $P_2$ accepts by final state what $P$ accepts by empty stack.
- $P$에서 new start state $s$ 와 final state $f$ 를 추가한다($P_2$는 $f$를 유일한 최종 상태로 갖는다. 다시 말해, F = ${\{f}\}$이다.)
- 아래의 전이 규칙들을 추가한다.
- $\delta(s,\epsilon,X_0)={\{(q,Z_0X_0)}\}$
- $\delta(p,\epsilon,X_0) = {\{(f,\epsilon)}\}$
- $\delta(q,\epsilon,X_0) ={\{(f,\epsilon)}\}$
- Convert the grammar
$S \rightarrow 0S1 \mid A$
$A \rightarrow 1A0 \mid S \mid \epsilon$
to a PDA that accepts the same language by empty stack.
PDA $P = ({\{q}\},{\{0,1}\},{\{0,1,A,S}\},\delta,q,S)$:
$\delta(q,\epsilon,S) = {\{(q,0S1),(q,A)}\}$
$\delta(q,\epsilon,A) = {\{(q,1A0),(q,S),(q,\epsilon)}\}$
$\delta(q,0,0) = {\{(q,\epsilon)}\}$
$\delta(q,1,1) = {\{(q,\epsilon)}\}$
- Convert the PDA of Excercise 1 to a context-free grammar.
$S$ = start symbol, $\epsilon$ = empty string, $Z = Z_0$이다.
$S \rightarrow [qZq][qZp]$
From rule(1)
$[qZq] \rightarrow 0[qXq][qZq]$
$[qZq] \rightarrow 0[qXp][pZq]$
$[qZp] \rightarrow 0[qXq][qZp]$
$[qZp] \rightarrow 0[qXp][pZp]$
From rule(2)
$[qXq] \rightarrow 0[qXq][qXq]$
$[qXq] \rightarrow 0[qXp][pXq]$
$[qXp] \rightarrow 0[qXq][qXp]$
$[qXp] \rightarrow 0[qXp][pXp]$
From rule(3)
$[qXq] \rightarrow 1[qXq]$
$[qXp] \rightarrow 1[qXp]$
From rule(4)
$[qXp] \rightarrow \epsilon$
From rule(5)
$[pXp] \rightarrow \epsilon$
From rule(6)
$[pXp] \rightarrow 1[pXq][qXp]$
$[pXp] \rightarrow 1[pXp][pXp]$
$[pXq] \rightarrow 1[pXq][qXq]$
$[pXq] \rightarrow 1[pXp][pXq]$
From rule(7)
$[pZp] \rightarrow 1$