Formal Language and Automata Homework 10

   

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

       

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

       

  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. Give algorithm to decide the following :

a) Is $L(G)$ finite, for a given CFG $G$? Hint: Use the pumping lemma.

b) Does $L(G)$ contain at least 100 strings, for a given CFG $G$?

   

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