- Submission Guideline: Upload your homework file (
hw9_[your student id].doc
,hw9_[your student id].hwp
orhw9_[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, Wednesday, November 10
Please feel free to leave your questions about homework problems in the online Eruri 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 Exercise 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 Exercise 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$