 Solution

Fix a finite alphabet $\Sigma$. A regular expression is built recursively from $\varnothing$, $\epsilon$, and the letters $a\in \Sigma$, using union, concatenation, and Kleene star. Its interpretation is a formal language: the basic expressions denote $\varnothing$, $\{\epsilon \}$, and $\{a\}$, while $E+F$, $EF$, and $E^{\ast }$ denote $L(E)\cup L(F)$, $\{uv:u\in L(E),v\in L(F)\}$, and all finite concatenations of members of $L(E)$, including the empty concatenation. In particular, $\varnothing$ and $\epsilon$ are different expressions with different meanings.

Kleene theorem identifies exactly the languages described by regular expressions with those recognized by finite-state automata. Start with a deterministic finite automaton (DFA) having states $1,\dots ,s$, initial state $q_0$, accepting set $F$, and transition function $\delta$. Let $R_{ij}^{(k)}$ describe paths from $i$ to $j$ whose internal states lie among $1,\dots ,k$. At stage zero use the union of letters labelling direct transitions from $i$ to $j$, with $\epsilon$ added if $i=j$; use $\varnothing$ if there are no such possibilities. Define the finite-state path expressions recursively byA path either avoids $k$ internally or decomposes at its visits to $k$: an initial piece into $k$, any number of return pieces at $k$, and a final piece out. Each piece has no internal occurrence of $k$. This proves the recursion by induction, including paths with $i=k$ or $j=k$, where empty pieces are permitted. Thusis a regular expression for the DFA's accepted formal language. An empty accepting set gives the expression $\varnothing$. This is the path form of state elimination for finite automata.

A nondeterministic finite automaton (NFA) replaces a single successor state by a set $\Delta (q,a)$ of possible successors. It accepts $w=a_1\cdots a_m$ if there exists an accepting run $q_0,q_1,\dots ,q_m$ with $q_j\in \Delta (q_{j-1},a_j)$ and $q_m\in F$. Rejection means that no accepting run exists, rather than that some run rejects. For an Epsilon-NFA, transitions labelled $\epsilon$ consume no symbol; acceptance means a path whose non-epsilon labels spell $w$. In particular, acceptance of the empty word is tested using the epsilon closure of the initial state.

The same Kleene theorem holds for nondeterministic finite automata. For an NFA without epsilon transitions, the powerset construction has state set $\mathcal{P}(Q)$, initial state $\{q_0\}$, transition $S\mapsto {\bigcup }_{q\in S}\Delta (q,a)$ on letter $a$, and accepting subsets meeting $F$. Induction on word length shows that its state is exactly the set of possible current NFA states. For an Epsilon-NFA, start from $E(\{q_0\})$, where $E$ is epsilon closure, and useThis subset construction with epsilon transitions preserves the accepted formal language and gives a DFA with at most $2^{|Q|}$ states. The already proved direction of Kleene theorem therefore gives a regular expression for every NFA language.

For the converse, recursively construct an Epsilon-NFA with a designated initial state and final state for a regular expression. Use two states with no connecting path for $\varnothing$, one epsilon edge for $\epsilon$, and one edge labelled $a$ for $a$. Keep component state sets disjoint. Union uses a fresh initial state with epsilon edges into both components, and epsilon edges from their finals to a fresh final. Concatenation joins the first final to the second initial by an epsilon edge. For Kleene star, use fresh initial and final states, an epsilon edge directly between them for zero iterations, an edge into the old initial, and epsilon edges from the old final both back to the old initial and out to the new final. Each construction has exactly the intended union, concatenation, or iteration semantics. Induction on the regular expression proves correctness; the subset construction with epsilon transitions then gives a DFA. This proves both directions of Kleene theorem.