Intro to Theory of Computation

Suppose that two finite automata \[ M_1 = (Q_1, \Sigma, \delta_1, q_{0_1}, F_1) \] and \[ M_2 = (Q_2, \Sigma, \delta_2, q_{0_2}, F_2) \] recognize the regular languages \(A_1\) and \(A_2\), respectively.

We construct \(M_3\) to recognize \(A_1 \cup A_2\) as follows: \[ M_3 = (Q_3, \Sigma, \delta_3, q_{0_3}, F_3) \] where \[ \begin{align*} Q_3 &= Q_1 \times Q_2 \\\\ &= \{(q_1, q_2) \mid q_1 \in Q_1 \text{ and } q_2 \in Q_2\}, \end{align*} \] \[ \delta_3((q_1, q_2), a) = (\delta_1(q_1, a), \delta_2(q_2, a)) \quad \forall a \in \Sigma, \] \[ q_{0_3} = (q_{0_1}, q_{0_2}), \] \[ F_3 = \{(q_1, q_2) \mid q_1 \in F_1 \text{ or } q_2 \in F_2 \}, \] which is the same as \((F_1 \times Q_2) \cup (Q_1 \times F_2)\).

Verification.
The key claim is the following: for any input string \(w\), after \(M_3\) reads \(w\), its state is exactly \((r_1, r_2)\), where \(r_i\) is the state \(M_i\) reaches after reading \(w\). The claim follows by a straightforward induction on \(|w|\). The crucial point is that \(\delta_3\) acts component-wise, updating the first component by \(\delta_1\) and the second by \(\delta_2\), independently of each other. Once this claim is established, the acceptance condition unfolds as \[ \begin{align*} M_3 \text{ accepts } w &\iff (r_1, r_2) \in F_3 \\\\ &\iff r_1 \in F_1 \text{ or } r_2 \in F_2 \\\\ &\iff M_1 \text{ accepts } w \text{ or } M_2 \text{ accepts } w. \end{align*} \] Therefore \(L(M_3) = A_1 \cup A_2\), proving that \(A_1 \cup A_2\) is regular.

Let \(N = (Q, \Sigma, \delta, q_0, F)\) be an NFA. The key idea is that since \(N\) can be in several states simultaneously, a single state of the equivalent DFA should encode which subset of \(Q\) the NFA is currently in. We first treat the case without \(\epsilon\)-transitions. The general case is handled by a small modification described at the end.

Construct \(D = (Q', \Sigma, \delta', q_0', F')\) as follows:

• \(Q' = \mathcal{P}(Q)\). Each DFA state is a subset of NFA states.
• \(\delta'(R, a) = \displaystyle\bigcup_{r \in R} \delta(r, a)\). From a subset \(R\), the new subset is the union of all states reachable from any \(r \in R\) on input \(a\).
• \(q_0' = \{q_0\}\). The DFA starts in the singleton subset containing the NFA's start state.
• \(F' = \{R \subseteq Q \mid R \cap F \neq \emptyset\}\). A subset is accepting if it contains at least one NFA accept state.

Correctness. By induction on the length of the input, one shows that after reading \(w = w_1 w_2 \cdots w_n\), the DFA \(D\) is in the state \(R_n \subseteq Q\) consisting of exactly those NFA states that \(N\) can reach after reading \(w\). Therefore \(D\) accepts \(w\) if and only if some such reachable state lies in \(F\), which is precisely the condition for \(N\) to accept \(w\). Hence \(L(D) = L(N)\).

Handling \(\epsilon\)-transitions. For each \(R \subseteq Q\), define the \(\epsilon\)-closure \(E(R)\) as the set of all states reachable from \(R\) by following zero or more \(\epsilon\)-transitions. Modify the construction by setting \(\delta'(R, a) = E\bigl(\bigcup_{r \in R} \delta(r, a)\bigr)\) and \(q_0' = E(\{q_0\})\). The same inductive argument then carries through.

The proof is by structural induction on the regular expression \(R\). The base cases (1, 2, 3) handle the atomic regexes built without combination. The inductive cases (4, 5, 6) build an NFA for \(R\) from NFAs for the smaller subexpressions \(R_1, R_2\). For each case, we exhibit an NFA \(M\) recognizing \(L(R)\), which establishes regularity (since any language recognized by an NFA is regular by Theorem 2).

1. \(R = a\) for some \(a \in \Sigma\):
   Then \[ L(R) = \{a\} \] and the following NFA recognizes \(L(R)\): \[ M = (\{q_0 , q_1\}, \Sigma, \delta, q_0, \{q_1\}) \] where \(\delta(q_0, a) = \{q_1\}\) and \(\delta(r, b) = \emptyset\) for \(r \neq q_0\) or \(b \neq a\).
2. \(R =\epsilon\):
   Then \[ L(R) = \{\epsilon\} \] and the following NFA recognizes \(L(R)\): \[ M = (\{q_0\}, \Sigma, \delta, q_0, \{q_0\}) \] where \(\delta(r, b) = \emptyset\) for any \(r\) and \(b\).
3. \(R = \emptyset\):
   Then \[ L(R) = \emptyset \] and the following NFA recognizes \(L(R)\): \[ M = (\{q\}, \Sigma, \delta, q, \emptyset) \] where \(\delta(r, b) = \emptyset\) for any \(r\) and \(b\).


For cases 4, 5, and 6, let \(M_1 = (Q_1, \Sigma, \delta_1, q_{0_1}, F_1)\) be an NFA that recognizes \(L(R_1)\) and \(M_2 = (Q_2, \Sigma, \delta_2, q_{0_2}, F_2)\) be an NFA that recognizes \(L(R_2)\). We assume that the state sets \(Q_1\) and \(Q_2\) are disjoint.

4. \(R = (R_1 \cup R_2)\):
   Then \[ L(R) = L(R_1) \cup L(R_2) \] and the following NFA recognizes \(L(R)\): \[ M = ( Q_1 \cup Q_2 \cup \{q_0\}, \Sigma, \delta, q_0, F_1 \cup F_2) \] where \(q_0\) is a new state not in \(Q_1 \cup Q_2\) and, for any \(q \in Q_1 \cup Q_2 \cup \{q_0\}\) and any \(a \in \Sigma_{\epsilon}\), \[ \delta(q, a) = \begin{cases} \delta_1(q, a) &\text{if \(q \in Q_1\)}, \\ \delta_2(q, a) &\text{if \(q \in Q_2\)}, \\ \{q_{0_1}, q_{0_2}\} &\text{if \(q = q_0\) and \(a = \epsilon\)}, \\ \emptyset &\text{if \(q = q_0\) and \(a \neq \epsilon\)}. \end{cases} \]

   Verification.
   On input \(w\), \(M\) starts at \(q_0\) and immediately \(\epsilon\)-branches into both \(q_{0_1}\) and \(q_{0_2}\), after which the two branches process \(w\) as \(M_1\) and \(M_2\) independently. Since the accept set is \(F_1 \cup F_2\), the machine \(M\) accepts \(w\) if and only if at least one of \(M_1, M_2\) accepts \(w\), that is, if and only if \(w \in L(R_1) \cup L(R_2)\).


5. \(R = (R_1 \circ R_2)\):
   Then \[ L(R) = L(R_1) \circ L(R_2) \] and the following NFA recognizes \(L(R)\): \[ M = ( Q_1 \cup Q_2 , \Sigma, \delta, q_{0_1}, F_2) \] where for any \(q \in Q_1 \cup Q_2\) and any \(a \in \Sigma_{\epsilon}\), \[ \delta(q, a) = \begin{cases} \delta_1(q, a) &\text{if \(q \in Q_1\) and \(q \not\in F_1\) }, \\ \delta_1(q, a) &\text{if \(q \in F_1\) and \(a \neq \epsilon\) }, \\ \delta_1(q, a) \cup \{q_{0_2}\} &\text{if \(q \in F_1\) and \(a = \epsilon\) }, \\ \delta_2(q, a) &\text{if \(q \in Q_2\) }. \end{cases} \]

   Verification.
   On input \(w\), \(M\) starts at \(q_{0_1}\) and processes \(w\) as \(M_1\). Whenever the computation enters an \(F_1\) state, an \(\epsilon\)-transition to \(q_{0_2}\) becomes available, and the NFA may nondeterministically either take it or continue inside \(M_1\). Once it jumps, the rest of \(w\) is processed as \(M_2\). Since the accept set is \(F_2\) only, \(M\) accepts \(w\) if and only if \(w\) splits as \(w = uv\) with \(u \in L(R_1)\) and \(v \in L(R_2)\), that is, if and only if \(w \in L(R_1) \circ L(R_2)\).


6. \(R = (R_1^*) \):
   Then \[ L(R) = L(R_1)^* \] and the following NFA recognizes \(L(R)\): \[ M = ( Q_1 \cup \{q_0\}, \Sigma, \delta, q_0, \{q_0\} \cup F_1) \] where \(q_0\) is a new state not in \(Q_1\) and, for any \(q \in Q_1 \cup \{q_0\}\) and any \(a \in \Sigma_{\epsilon}\), \[ \delta(q, a) = \begin{cases} \delta_1(q, a) &\text{if \(q \in Q_1\) and \(q \not\in F_1\) }, \\ \delta_1(q, a) &\text{if \(q \in F_1\) and \(a \neq \epsilon\) }, \\ \delta_1(q, a) \cup \{q_{0_1}\} &\text{if \(q \in F_1\) and \(a = \epsilon\) }, \\ \{q_{0_1}\} &\text{if \(q = q_0\) and \(a = \epsilon\) }, \\ \emptyset &\text{if \(q=q_0\) and \(a \neq \epsilon\)}. \end{cases} \]

   Verification.
   The new start state \(q_0\) is itself accepting, so on input \(\epsilon\) the machine \(M\) immediately accepts (and \(\epsilon \in L(R_1)^*\) holds for any \(R_1\)). On a non-empty input, \(M\) first \(\epsilon\)-transitions to \(q_{0_1}\) and runs \(M_1\). Whenever \(M_1\) reaches an \(F_1\) state, an \(\epsilon\)-transition back to \(q_{0_1}\) allows another iteration of \(R_1\), and this loop can be repeated any number of times. Hence \(M\) accepts \(w\) if and only if \(w\) splits as \(w = w_1 w_2 \cdots w_k\) with \(k \geq 0\) and each \(w_i \in L(R_1)\), that is, if and only if \(w \in L(R_1)^*\).

For the converse direction, suppose \(A\) is regular, so a DFA \(M\) recognizes \(A\). We must produce a regular expression \(R\) with \(L(R) = A\). The construction proceeds via an intermediate object called a generalized NFA (GNFA), in which transitions are labeled by regular expressions rather than single symbols. A GNFA reads input by consuming, on each transition, any string matching that transition's regex label.

Step 1: Convert \(M\) into a GNFA.
Add a new start state \(s\) with an \(\epsilon\)-edge to \(M\)'s start state, and a new unique accept state \(t\) with \(\epsilon\)-edges from each of \(M\)'s accept states. Call every state other than \(s\) and \(t\) internal. Finally, for every ordered pair \((q_i, q_j)\) with \(q_i \neq t\) and \(q_j \neq s\), merge the transitions from \(q_i\) to \(q_j\) into one labeled by the union of their labels, and add a transition labeled \(\emptyset\) where there was none. The resulting GNFA recognizes exactly \(A\).

Step 2: State elimination.
Repeatedly remove internal states one at a time. To remove an internal state \(q_{\mathrm{rip}}\), update each remaining transition \(q_i \to q_j\) (for \(q_i \neq t\) and \(q_j \neq s\)) by replacing its old label \(R_{ij}\) with \[ R_{ij}^{\text{new}} = R_{ij} \cup R_{i,\mathrm{rip}} \, R_{\mathrm{rip},\mathrm{rip}}^* \, R_{\mathrm{rip},j}. \] In words, the first term bypasses \(q_{\mathrm{rip}}\) entirely, while the second passes from \(q_i\) into \(q_{\mathrm{rip}}\), loops there, and then continues to \(q_j\). This new label captures every path that previously went through \(q_{\mathrm{rip}}\). The Kleene star is essential here, since it accounts for traversing the self-loop at \(q_{\mathrm{rip}}\) any number of times.

Step 3: Read off the regex.
After all internal states are eliminated, only \(s\) and \(t\) remain, connected by a single transition labeled with some regex \(R\). One can verify that each elimination step preserves the recognized language, so the final \(R\) satisfies \(L(R) = A\).