Intro to Theory of Computation

Suppose we have 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). \] These can recognize regular languages \(A_1\) and \(A_2\) respectively.

Here, we can 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 \[ Q_3 = Q_1 \times Q_2 = \{(q_1, q_2)\, | \, q_1 \in Q_1 \text{ and } q_2 \in Q_2\} \]

\[ \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) \,| \, 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\). This follows by a straightforward induction on \(|w|\), the crucial point being that \(\delta_3\) acts component-wise — at every step, the first component is updated by \(\delta_1\) and the second by \(\delta_2\) independently. Once this claim is established, the acceptance condition unfolds as \[ 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. \] 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. \(\blacksquare\)

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 for any \(q \in Q\) 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 iff at least one of \(M_1, M_2\) accepts \(w\), i.e., iff \(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\) 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 computation enters an \(F_1\) state, an \(\epsilon\)-transition to \(q_{0_2}\) becomes available — the NFA may nondeterministically take this transition 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 iff \(w\) splits as \(w = uv\) with \(u \in L(R_1)\) and \(v \in L(R_2)\), i.e., iff \(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 for any \(q \in Q\) 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\); this can be repeated any number of times. Hence \(M\) accepts iff \(w\) splits as \(w = w_1 w_2 \cdots w_k\) with \(k \geq 0\) and each \(w_i \in L(R_1)\), i.e., iff \(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. Then ensure that every pair of internal states \((q_i, q_j)\) has exactly one transition between them (labeled by the union of all symbols that previously triggered \(q_i \to q_j\) in \(M\), or by the regex \(\emptyset\) if no such symbol existed). 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} \] — that is, "either bypass \(q_{\mathrm{rip}}\) entirely (old label), or detour through \(q_{\mathrm{rip}}\) any number of times before continuing." This new label captures every path that previously went through \(q_{\mathrm{rip}}\). The Kleene star is essential here: it accounts for self-loops at \(q_{\mathrm{rip}}\) being traversed 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\). \(\blacksquare\)