- Submission Guideline: Upload your homework file (
hw10_[your student id].doc
,hw10_[your student id].hwp
orhw10_[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, Tuesday, November 22
Please feel free to leave your questions about homework problems in the online Piazza classroom.
- 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 \}$.
- 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$?
- 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$.