- Submission Guideline: Upload your homework file (
hw2_[your student id].doc
orhw2_[your student id].hwp
) to online Uclass classroom. You are allowed to write down your answers either in Korean or English at your convenience. - Deadline: 23:59 PM, Wednesday, June 5
Please feel free to leave your questions about homework problems in the online Uclass classroom.
- Design context-free grammars for the following languages.
(a) The set of all strings of $a$’s and $b$’s that are not of the form $ww$, that is, not equal to any string repeated.
(b) The set of all strings with twice as many $0$’s as $1$’s.
- The following grammar generates the language of regular expression $0^* 1(0+1)^* $ :
$S \rightarrow A1B$
$A \rightarrow 0A \mid \epsilon$
$B \rightarrow 0B\mid 1B\mid \epsilon$
Give leftmost and rightmost derivations of the following strings:
(a) $00101$.
(b) $1001$.
(c) $00011$.
- For the grammar and each of the strings in Problem 2, give parse trees.
- Consider the set of all strings of balanced parentheses of two types, round and square. An example of where these strings come from is as follows: $f(a[i]*(b[i][j],c[g(x)]),d[i])$. It becomes the balanced-parenthesis string $([\; ]([\; ] [\; ][ () ])[\; ])$.
Design a grammar for all and only the strings of round and square parenthesis that are balanced.
- Consider the grammar $S \rightarrow aS\mid aSbS\mid \epsilon$.
This grammar is ambiguous. Show in particular that the string $aab$ has two:
(a) Parse trees.
(b) Leftmost derivations.
(c) Rightmost derivations.
- 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 Problem 6.
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 Problem 6 to a context-free grammar.