- Submission Guideline: Upload your homework file (
hw7_[your student id].doc
,hw7_[your student id].hwp
orhw7_[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.
- 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$
- 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.
- 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.
- 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.
- Convert the PDA of Excercise 1 to a context-free grammar.