• Submission Guideline: Upload your homework file (hw1_[your student id].doc or hw1_[your student id].hwp) 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, September 14
• Note 1: A language $\overline{L}$ is a complement of a language $L$. In other words, for a language $L \subseteq \Sigma^* $, $\overline{L} = \Sigma^* - L$.
• Note 2: A language $L^R$ is a reversal of a language $L$. A reversal means that we reverse the order of characters in a string. For instance, if $w = abcd$, then the reversal of $w$ is $w^R = dcba$. A reversal of a language $L$ is defined as $L^R = \{ w^R \mid w \in L \}$.

       

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

   

1. Show that for all sets $S$ and $T, S-T = S \cap \overline{T}$.
2. Show that $S_1 = S_2$ if and only if $S_1\cup S_2 = S_1 \cap S_2$.
3. Show that if $S_1$ and $ S_2$ are finite sets with $\lvert S_1 \rvert = n$ and $\lvert S_2 \rvert = m$, then $\lvert S_1 \cup S_2 \rvert \leq n+m$.
4. Show that $S_1 = S_2$ if and only if $(S_1 \cap \overline{S_2}) \cup (\overline{S_1} \cap S_2) = \emptyset$.
5. Show that $S_1 \cup S_2 -(S_1 \cap \overline{S_2}) = S_2$.
6. Show that $\sum_{i=0}^n 2^i = 2^{n+1}-1.$
7. Show that $\sum_{i=1}^n \frac{1}{i^2} \leq 2-\frac{1}{n}.$
8. Let $\Sigma = \{ a,b \}$ and $L= \{ aa,bb \} $. Use set notation to describe $\overline{L}$.
9. Are there languages for which $\overline{L^* }=(\overline{L})^*$?
10. Prove or disprove the following claims. $(L_1 \cup L_2)^R = L_1^R\cup L_2^R$ for all languages $L_1$ and $L_2.$