- Submission Guideline: Upload your homework file (
hw3_[your student id].doc
orhw3_[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, Friday, June 14
Please feel free to leave your questions about homework problems in the online Uclass classroom.
- Begin with the grammar :
$S \rightarrow ASB \mid \epsilon$
$A \rightarrow aAS \mid a$
$B\rightarrow SbS \mid A \mid bb$
a) Eliminate $\epsilon$-productions.
b) Eliminate any unit productions in the resulting grammar.
c) Eliminate useless symbols in the resulting grammar.
d) Put the resulting grammar into Chomsky Normal Form.
- Repeat Problem 1 for the following grammar :
$S \rightarrow 0A0 \mid 1B1 \mid BB$
$A \rightarrow C$
$B \rightarrow S \mid A$
$C \rightarrow S \mid \epsilon$
- Repeat Problem 1 for the following grammar:
$S \rightarrow AAA\mid B$
$A\rightarrow aA \mid B$
$B\rightarrow \epsilon$
- Let $G$ be an $\epsilon$-production-free grammar whose total length of production bodies is $n$. We convert $G$ to CNF.
a) Show that the CNF grammar has at most $O(n^2)$ productions.
b) Show that it is possible for the CNF grammar to have a number of productions proportional to $n^2$. Hint: Consider the construction that eliminates unit productions.
- Use the CFL pumping lemma to show each of these languages not to be context-free:
a) ${\{a^ib^jc^k \mid i < j<k}\}$.
b) ${\{0^i1^j\mid j=i^2}\}$.
- When we try to apply the pumping lemma to a CFL, the adversary wins, and we cannot complete the proof. Show what goes wrong when we choose $L$ to be one of the following languages:
a) ${\{0^n1^n \mid n\geq 1}\}$.
b) The set of palindromes over alphabet ${\{0,1}\}$.
- Example : $00100, 11,10101 \in L$ and $110,01101,111000 \notin L$
- Show that the CFL’s are closed under the following operations :
a) $init(L) = \{ w \mid$ for some $x, wx$ is in $L \}$.
Hint: Start with a CNF grammar for the language $L$.
b) The operation $L/a$, the quotient of $L$ and $a$, is the set of strings $w$ such that $wa$ is in $L$. For example, if $L={\{a, aab,baa}\}$, then $L/a ={\{\epsilon, ba}\}$.
Hint: Again, start with a CNF grammar for $L$.
- Consider the following two language :
$L_1 = {\{a^nb^{2n}c^m \mid n,m\ge0}\}$
$L_2 = {\{a^nb^mc^{2m} \mid n,m\ge0}\}$
a) Show that each of these languages is context-free by giving grammars for each.
b) Is $L_1 \cap L_2$ a CFL? Justify your answer.
- Show that the CFL’s are not closed under the following operations :
a) $min(L) = \{w \mid w$ is in $L$, but no proper prefix of $w$ is in $L \}$.
b) $max(L) = \{w \mid w$ is in $L$ and for no $x$ other than $\epsilon$ is $wx$ is $L \}$.
- The following are the productions of a CNF grammar $G$ :
$S \rightarrow AB\mid BC$
$A \rightarrow BA\mid a$
$B \rightarrow CC\mid b$
$C \rightarrow AB\mid a$
Use the CYK algorithm to determine whether each of the following strings is in $L(G)$ :
a) $ababa$.
b) $baaab$.