Formal Language and Automata Homework 7

   

  • Submission Guideline: Upload your homework file (hw7_[your student id].doc, hw7_[your student id].hwp or hw7_[your student id].pdf) to online Eruri classroom. You are allowed to write down your answers either in Korean or English at your convenience.
  • Deadline : 18:00 PM, Friday, November 4

       

Please feel free to leave your questions about homework problems in the online Piazza classroom.

       

  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$

b) $0011$

c) $010$

   

  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.

b) The set of all strings of $0$’s and $1$’s with an equal number of $0$’s and $1$’s.

   

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

b) Find a PDA $P_2$ such that $L(P_2) = N(P)$; i.e., $P_2$ accepts by final state what $P$ accepts by empty stack.

   

  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.

   

  1. Convert the PDA of Excercise 1 to a context-free grammar.