- Submission Guideline: Upload your homework file (
hw5_[your student id].doc
,hw5_[your student id].hwp
orhw5_[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, October 12
Please feel free to leave your questions about homework problems in the online Eruri classroom.
- 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)$?
- 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.
- 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.