Martin

For every alphabet $\Sigma$, every regular language over $\Sigma$ can be accepted by a finite automaton.

Because of Theorems 3.17 and 3.18, it’s enough to show that every regular language over $\Sigma$ can be accepted by an NFA. The set of regular languages over $\Sigma$ is defined recursively in Definition 3.1, and we will prove the theorem by structural induction.

The languages $\varnothing$ and $\{\sigma\}$ (where $\sigma\in\Sigma$) can be accepted by the two NFAs in Figure 3.26, respectively. The induction hypothesis is that $L_1$ and $L_2$ are both regular languages over $\Sigma$ and that for both $i=1$ and $i=2$, $L_i$ can be accepted by an NFA $M_i=(Q_i,\Sigma,q_i,A_i,\delta_i)$. We can assume, by renaming states if necessary, that $Q_1$ and $Q_2$ are disjoint. In the induction step we must show that there are NFAs accepting the three languages $L(M_1)\cup L(M_2)$, $L(M_1)L(M_2)$, and $L(M_1)^*$.

In each case we will give an informal definition and a diagram showing the idea of the construction. For simplicity, each diagram shows the two NFAs $M_1$ and $M_2$ as having two accepting states, both distinct from the initial state.

An NFA $M_u$ accepting $L(M_1)\cup L(M_2)$ is shown in Figure 3.27a. Its states are those of $M_1$ and $M_2$ and one additional state $q_u$ that is the initial state. The transitions include all the ones in $M_1$ and $M_2$ as well as $\Lambda$-transitions from $q_u$ to $q_1$ and $q_2$, the initial states of $M_1$ and $M_2$. Finally, the accepting states are simply the states in $A_1\cup A_2$.

If $x\in L(M_1)$, for example, $M_u$ can accept $x$ by taking the $\Lambda$-transition from $q_u$ to $q_1$ and then executing the moves that would allow $M_1$ to accept $x$. On the other hand, if $x$ is any string accepted by $M_u$, there is a path from $q_u$ to an element of $A_1$ or $A_2$. The first transition in the path must be a $\Lambda$-transition, which takes $M_u$ to $q_1$ or $q_2$. Because $Q_1\cap Q_2=\varnothing$, the remainder of the path causes $x$ to be accepted either by $M_1$ or by $M_2$.

An NFA $M_c$ accepting $L(M_1)L(M_2)$ is shown in Figure 3.27b. No new states need to be added to those of $M_1$ and $M_2$. The initial state is $q_1$, and the accepting states are the elements of $A_2$. The transitions include all those of $M_1$ and $M_2$ and a new $\Lambda$-transition from every element of $A_1$ to $q_2$. If $x$ is the string $x_1x_2$, where $x_i$ is accepted by $M_i$ for each $i$, then $M_c$ can process $x$ by moving from $q_1$ to a state in $A_1$ using $\Lambda$’s and the symbols of $x_1$, taking the $\Lambda$-transition to $q_2$, and moving to a state in $A_2$ using $\Lambda$’s and the symbols of $x_2$. Conversely, if $x$ is a string accepted by $M_c$, then at some point during the computation, $M_c$ must execute the $\Lambda$-transition from an element of $A_1$ to $q_2$. If $x_1$ is the prefix of $x$ whose symbols have been processed at that point, then $x_1$ must be accepted by $M_1$; the remaining suffix of $x$ is accepted by $M_2$, because it corresponds to a path from $q_2$ to an element of $A_2$ that cannot involve any transitions other than those of $M_2$.

Finally, an NFA $M_k$ accepting $L(M_1)^*$ is shown in Figure 3.27c. Its states are the elements of $Q_1$ and a new initial state $q_k$ that is also the only accepting state. The transitions are those of $M_1$, a $\Lambda$-transition from $q_k$ to $q_1$, and a $\Lambda$-transition from every element of $A_1$ to $q_k$. We can see by structural induction that every element of $L(M_1)^*$ is accepted. The null string is, because $q_k$ is an accepting state. Now suppose that $x\in L(M_1)^*$ is accepted and that $y\in L(M_1)$. When $M^*$ is in a state in $A_1$ after processing $x$, it can take a $\Lambda$-transition to $q_k$ and another to $q_1$, process $y$ so as to end up in an element of $A_1$, and finish up by returning to $q_k$ with a $\Lambda$-transition. Therefore, $xy$ is accepted by $M^*$.

We can argue in the opposite direction by using mathematical induction on the number of times $M^*$ enters the state $q_k$ in the process of accepting a string. If $M^*$ visits $q_k$ only once in accepting $x$, then $x=\Lambda$, which is an element of $L(M_1)^*$. If we assume that $n\ge1$ and that every string accepted by $M^*$ that causes $M^*$ to enter $q_k$ $n$ or fewer times is in $L(M_1)^*$, then consider a string $x$ that causes $M^*$ to enter $q_k$ $n+1$ times and is accepted. Let $x_1$ be the prefix of $x$ that is accepted when $M^*$ enters $q_k$ the $n$th time, and let $x_2$ be the remaining part of $x$. By the induction hypothesis, $x_1\in L(M_1)^*$. In processing $x_2$, $M^*$ moves to $q_1$ on a $\Lambda$-transition and then from $q_1$ to an element of $A_1$ using $\Lambda$-transitions in addition to the symbols of $x_2$. Therefore, $x_2\in L(M_1)$, and it follows that $x\in L(M_1)^*$.

The three portions of the induction step in the proof of Theorem 3.25 provide algorithms for constructing an NFA corresponding to an arbitrary regular expression. These can be combined into a general algorithm that could be used to automate the process.

The transition diagram in Figure 3.29a shows a literal application of the three algorithms in the case of the regular expression $((aa+b)^*(aba)^*bab)^*$. In this case there is no need for all the $\Lambda$-transitions that are called for by the algorithms, and a simplified NFA is shown in Figure 3.29b. At least two $\Lambda$-transitions are still helpful in order to preserve the resemblance between the transition diagram and the regular expression. The algorithms can often be shortened in examples, but for each step where one of them calls for an extra state and/or a $\Lambda$-transition, there are examples to show that dispensing with the extra state or the transition doesn’t always work (see Exercises 3.45–3.48).