- Submission Guideline: Upload your homework file (
hw4_[your student id].doc
,hw4_[your student id].hwp
orhw4_[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 5
Please feel free to leave your questions about homework problems in the online Eruri classroom.
- 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}\}$.
- 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.
- When we try to apply the pumping lemma to a regular language, the adversary wins, and we cannot complete the proof. Show what goes wrong when we choose $L$ to be one of the following languages.
a) ${\{00,11}\}$
b) $(00+11)^*$
- Suppose $L$ is a regular language with alphabet $\Sigma$. Given an algorithm to tell whether $L = \Sigma^*$, i.e, all strings over its alphabet.
- Give an algorithm to tell whether two regular languages $L_1$ and $L_2$ have at least one string in common.
6.
state | $0$ | $1$ | |
---|---|---|---|
$\rightarrow$ | $A$ | $B$ | $A$ |
$B$ | $A$ | $C$ | |
$C$ | $D$ | $B$ | |
* | $D$ | $D$ | $A$ |
$E$ | $D$ | $F$ | |
$F$ | $G$ | $E$ | |
$G$ | $F$ | $G$ | |
$H$ | $G$ | $D$ |
a) Draw the table of distinguishabilities for this automaton.
b) Construct the minimum-state equivalent DFA.
7.
state | $0$ | $1$ | |
---|---|---|---|
$\rightarrow$ | $A$ | $B$ | $E$ |
$B$ | $C$ | $F$ | |
* | $C$ | $D$ | $H$ |
$D$ | $E$ | $H$ | |
$E$ | $F$ | $I$ | |
* | $F$ | $G$ | $B$ |
$G$ | $H$ | $B$ | |
$H$ | $I$ | $C$ | |
* | $I$ | $A$ | $E$ |
a) Draw the table of distinguishabilities for this automaton.
b) Construct the minimum-state equivalent DFA.