---
tags: Formal Language 2019
title: HW-02
---

<style>
img {
margin: auto;
display: block;
}
</style>

# FORMAL Language 2019 HW-2
## Problem 1
Convert the nfa defined by
$$
\begin{array}{lll}
\delta(q_0,a)=\{q_0,q_1\}\\
\delta(q_1,b)=\{q_1,q_2\}\\
\delta(q_2,a)=\{q_2\}\\
\end{array}
$$
with initial state $q_0$ and final state $q_2$ into an equivalent dfa.

==**Solution**== This gives the dfa


---
## Problem 2
Convert the nfa defined by
$$
\begin{array}{lll}
\delta(q_0,a)=\{q_0,q_1\}\\
\delta(q_1,b)=\{q_1,q_2\}\\
\delta(q_2,a)=\{q_2\}\\
\delta(q_0,\lambda)=\{q_2\}\\
\end{array}
$$
with initial state $q_0$ and final state $q_2$ into an equivalent dfa.

==**Solution**==


---
## Problem 3
Convert the nfa defined by
$$
\begin{array}{lll}
\delta(q_0,a)=\{q_0,q_1\}\\
\delta(q_1,b)=\{q_1,q_2\}\\
\delta(q_2,a)=\{q_2\}\\
\delta(q_1,\lambda)=\{q_1,q_2\}\\
\end{array}
$$
with initial state $q_0$ and final state $q_2$ into an equivalent dfa.

==**Solution**==


---
## Problem 4
Is it true that for eveny nfa $M=(Q,\Sigma,\delta,q_0,F)$, the complement of $L(M)$ is equal to the set $\{w\in \Sigma^* : \delta^*(q_0,w)\cap (Q-F)\ne \emptyset\}$?
If so, prove it; if not, give a counterexample.

==**Solution**== No.
$\lambda$-transition make a difference. See the following simple example, that $L = \{a\}$. But $\delta^*(q_0,a)\cap (Q-F)=\{q_2\}\neq\emptyset$ which is impossible.


---
## Problem 5
Prove that for every nfa with an arbitrary number of final states there is an equivalent nfa with only one final state. Can we make a similar claim for dfa's?

==**Solution**==
Introduce a new final state $p_f$ and for every $q\in F$ add thetransitions
$$\delta(q,\lambda) = \{p_f\}$$

Then make $p_f$ the only final state. It is a simple matter then to arguethat if $\delta^*(q_0,w)\in F$ originally, then $(q_0,w)=\{p_f\}$ after the modification, so both the original and the modified nfa's are equivalent.

Since this construction requires $\lambda$-transitions, it cannot be made fordfa's. Generally, it is impossible to have only one final state in a dfa,as can be seen by constructing a dfa that accepts $\{\lambda,a\}$.

---
## Problem 6
Prove that all finite languages are regular.

==**Solution**== Suppose that $L = \{w_1,w_2, ...w_m\}$. Then the nfa


acccepts $L$. Therefore, $L$ is regular.

---
## Problem 7
Show that if $L$ is regular, so is $L^R$.

==**Solution**== The construction is easy: reverse final and initial states and
all arrows. Then use the conclusion of Exercise $19$, Section $2.2$.

:::info
### $\S$ 2.2 Exercise 19
Consider the following modification of Definition $2.6$. An nfa with multiple initial states is defined by the quintuple
$$M = (Q,\Sigma ,\delta ,Q_0, F) ,$$
where $Q_0 \subseteq Q$ is a set of possible initial states. The language accepted by such an automaton is defined as
$$L (M) = \{w : \delta ^*(q_0,w)\mbox{ contains }q_f ,\mbox{ for any }q_0 \in Q_0, q_f \in F\}.$$
Show that for every nfa with multiple initial states there exists an nfa with a single initial state that accepts the same language.
\
**Solution:** Introduce a new initial state p0. Then add a transition
$$(p_0,\lambda ) = Q_0.$$
Next, remove starting state status from $Q_0$. It is straightforward to see that the new nfa is equivalent to the original one.
:::

---
## Problem 8
Consider the dfa with initial state $q_0$, final state $q_2$ and
$$
\begin{array}{lll}
\delta(q_0,a)=q_2, \delta(q_0,b)=q_2\\
\delta(q_1,a)=q_2, \delta(q_1,b)=q_2\\
\delta(q_2,a)=q_3, \delta(q_2,b)=q_3\\
\delta(q_3,a)=q_3, \delta(q_3,b)=q_1\\
\end{array}
$$
Find a minimal equivalent dfa.

==**Solution**== Using procedure mark, we generate the equivalence classes $\{q_0, q_1\}, \{q_2\}, \{q_3\}$. Then the procedure reduce gives
$$
\begin{array}{lll}
\hat\delta(01,a)=2,\ \hat\delta(01,b)=2,\\
\hat\delta(2,a)=3,\ \ \ \hat\delta(2,b)=3,\\
\hat\delta(3,a)=3,\ \ \ \hat\delta(3,b)=01.\\
\end{array}
$$

Therefore a minimal equivalent dfa is


---
## Problem 9
Find minimal dfa's for the following languages.
**A.** $L=\{a^n: n\ge 0, n\ne 2\}$

==**Solution**== The following graph is a four-state dfa that accepts the language $L=\{a_n:n\ge0,n\ne2\}$.


We claim it is a minimal dfa. Because $q_3\in F$ and $q2\notin F$, so $q_2$ and $q_3$ are distinguishable. Next $\delta(q_1,a)=q_2\in F$ and $\delta(q_2,a)=q_3\in F$, so $q_1$ and $q_2$ are distinguishable. Also, since $\delta^*(q_o,aa)=q2\notin F$ and $\delta(q_1,aa)=q_3\in F$, so $q_0$ and $q_1$ are distinguishable. Finally, $\delta(q_2,aa)=q_3\in F$, so $q_0$ and $q_2$ are also distinguishable.

This completes the check for distinguishable pairs required in procedure mark, and we see that all the four states are mutually distinguishable. Therefore,the dfa is minimal.

---
**B.** $L=\{a^n:n\ne 3 \mbox{ and } n\ne 4\}$

==**Solution**== The following graph is a six-state dfa that accepts the language $L=\{a^n:n\ne3 \mbox{ and}\ n\ne4\}$.


---
**C.** $L=\{a^n: n \mbox{ mod } 3 = 1\}\cup \{a^n: n\mod{ mod } 5=1\}$

==**Solution**== The following graph is a fifteen states dfa. This dfa accepts the
language $L=\{a^n:n\ \mbox{mod}\ 3=1\}\cup\{a^n:n\ \mbox{mod}\ 5=1\}$.


All the states are mutually distinguish and can be verified by performing the procedure mark. Therefore, the dfa is minimal.

---
## Problem 10 (class ex)
Find the minimal dfa that accept
$L(abb)^*\cdot L(a^*bb^*)$

==**Solution**== Start with


Then use the nfa-to-dfa algorithm and procedures $mark$ and $reduce$ in Chapter 2 to get the minimal dfa