Theory of Computation Homework 3

   

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

   

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

   

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

   

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

   

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

   

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

   

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