• Submission Guideline: Upload your homework file (hw1_[your student id].doc or hw1_[your student id].hwp) to online Uclass classroom. You are allowed to write down your answers either in Korean or English at your convenience.
• Deadline: 23:59 PM, Tuesday, April 23

       

Please feel free to leave your questions about homework problems in the online Uclass 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. Convert the following NFA to a DFA and informally describe the language it accepts.

	State	$0$	$1$
$\rightarrow $	$p$	${\{p,q}\}$	${\{p}\}$
	${q}$	${\{r,s}\}$	${\{t}\}$
	${r}$	${\{p,r}\}$	${\{t}\}$
$*$	${s}$	$\emptyset$	$\emptyset$
$*$	${t}$	$\emptyset$	$\emptyset$

   

5. Give NFA’s to accept the following languages. Try to take advantage of nondeterministic as much as possible.

   a) The set of strings over alphabet ${\{0,1,\ldots,9}\}$ such that the final digit has appeared before.

   b) The set of strings over alphabet ${\{0,1,\ldots,9}\}$ such that the final digit has not appeared before.

   c) The set of $0$’s and $1$’s such that there are two $0$’s separated by a number of positions that is a multiple of 4. Note that $0$ is an allowable multiple of 4.

   

6. Here is a transition table for a DFA.

	State	$0$	$1$
$\rightarrow $	$q_1$	$q_2$	$q_1$
	$q_2$	$q_3$	$q_1$
$*$	$q_3$	$q_3$	$q_2$

(a) Give all the regular expressions $R_{ij}^{(0)}$.

Note: Think of state $q_i$ as if were the state with integer number $i$.

(b) Give all the regular expressions $R_{ij}^{(1)}$. Try to simplify the expressions as much as possible.

(c) Give all the regular expressions $R_{ij}^{(2)}$. Try to simplify the expressions as much as possible.

(d) Give a regular expression for the language of automaton.

(e) Construct the transition diagram for the DFA and give a regular expression for its language by eliminating state $q_2$.

   

7. Convert the following DFA to a regular expression, using the state-elimination technique.

	State	$0$	$1$
$\rightarrow *$	$p$	$s$	$p$
	$q$	$p$	$s$
	$r$	$r$	$q$
	$s$	$q$	$r$

   

8. Prove that the following are not regular languages.

a) ${\{0^n10^n \mid n \geq 1}\}$.

b) $\{0^n 1^m 2^n \mid$ $n$ and $m$ are arbitary integers $\}$.

c) ${\{0^n1^{2n} \mid n \geq 1}\}$.

   

9. Prove that the following are not regular languages.

a) $\{0^n \mid$ $n$ is a perfect square $\}$.

b) $\{0^n \mid$ $n$ is a perfect cube $\}$.

c) $\{0^n \mid$ $n$ is a power of $2$ $\}$.

d) The set of string of $0$’s and $1$’s whose length is a perfect square.

   

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