Formal Language and Automata Homework 9

   

  • Submission Guideline: Upload your homework file (hw9_[your student id].doc, hw9_[your student id].hwp or hw9_[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 18

       

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

       

  1. 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.

   

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

   

  1. Repeat Exercise 1 for the following grammar:

$S \rightarrow AAA\mid B$

$A\rightarrow aA \mid B$

$B\rightarrow \epsilon$

   

  1. 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.

   

  1. 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}\}$.

   

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