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

       

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

       

1. Suppose $h$ is the homomorphism from the alphabet ${\{0,1,2}\}$ to the alphabet ${\{a,b}\}$ defined by: $h(0)=a$; $h(1)=ab$, and $h(2) = ba$.

a) What is $h(0120)$?

b) What is $h(21120)$?

c) If $L$ is the languages $L(01^*2)$, what is $h(L)$?

d) If $L$ is the languages $L(0+12)$, what is $h(L)$?

e) Suppose $L$ is the language ${\{ababa}\}$, that is, the languages consisting of only the one string $ababa$. What is $h^{-1}(L)$?

f) If $L$ is the languages $L(a(ba)^*)$, what is $h^{-1}(L)$?

   

2. If $L$ is a languages, and $a$ is a symbol, then $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}\}$. Prove that of $L$ is regular, so is $L / a$. Hint​ : Start with a DFA for $L$ and consider the set of accepting states.

   

3. If $L$ is a language, and $a$ is a symbol, then $a \backslash L $, is the set of strings $w$ such that $aw$ is in $L$. For example, if $L={\{a, aab, baa}\}$, then $a\backslash L = {\{\epsilon, ab}\}$. Prove that if $L$ is regular, so is $a \backslash L $. Hint : Remember that the regular languages are closed reversal and under the quotient operation of Exercise 2.