Formal Language and Automata Homework 7 Answer

       

  1. 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) $

7a

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

7b

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

7a

   

  1. 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)}\}$

   

  1. 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)}\}$

   

  1. 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)}\}$

   

  1. 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$