Kleene's Theorem

Statement

Kleene’s Theorem: A language $L \subseteq \Sigma^*$ is regular (recognised by a finite automaton) if and only if it is denoted by a regular expression.

$L \text{ is regular} \iff \exists \text{ regex } R. L = L(R)$

Two Directions

Part (a): Regex $\Rightarrow$ Automaton

Every regular expression can be converted to an equivalent NFA-$\varepsilon$.

Part (b): Automaton $\Rightarrow$ Regex

Every finite automaton can be converted to an equivalent regular expression.

Part (a): Regex to NFA

Construction by Induction

Base cases:

$\varepsilon$: NFA with one state, start = accept, no transitions.

$\xrightarrow{\quad} \textcircled{\scriptstyle q}$

$\emptyset$: NFA with one state, start state, no accepting states.

$\xrightarrow{\quad} q$

Symbol $a$: NFA with two states.

$\xrightarrow{\quad} q_0 \xrightarrow{a} \textcircled{\scriptstyle q_1}$

Inductive Constructions

Union $R_1 | R_2$:

• New start state $q_{\text{new}}$
• $\varepsilon$-transitions to starts of $M_1$ and $M_2$
• Accepting: $F_1 \cup F_2$

Concatenation $R_1 R_2$:

• $\varepsilon$-transitions from accept states of $M_1$ to start of $M_2$
• Start: start of $M_1$
• Accepting: $F_2$

Star $R^*$:

• New state $q_{\text{new}}$ (start and accepting)
• $\varepsilon$-transition to old start
• $\varepsilon$-transitions from old accepting states back to $q_{\text{new}}$

Part (b): NFA to Regex

The State Elimination Method

For automaton $M = (Q, \Sigma, \Delta, s, F)$, compute regular expression for each “region” of the automaton.

A region $(q, S, q')$ consists of:

• Start state $q$
• End state $q'$
• Set $S$ of intermediate states allowed

The regional language $L_M(q, S, q')$ contains strings taking $q$ to $q'$ through only states in $S$.

Recursive Definition

Base ($S = \emptyset$):

$L_M(q, \emptyset, q') = \begin{cases} \{\varepsilon\} \cup \{a : q \xrightarrow{a} q'\} & q = q' \\ \{a : q \xrightarrow{a} q'\} & q \neq q' \end{cases}$

This is a finite language, hence regular (expressible as finite union of regex).

Inductive step: Pick $q_0 \in S$. Define $S' = S \setminus \{q_0\}$.

$L_M(q, S, q') = L_M(q, S', q') \cup L_M(q, S', q_0) \cdot L_M(q_0, S', q_0)^* \cdot L_M(q_0, S', q')$

Intuition

Paths through $S$ either:

• Don’t visit $q_0$ at all: $L_M(q, S', q')$
• Visit $q_0$ at least once: go to $q_0$, loop zero or more times, go to $q'$

Final Expression

The language of $M$ is:

$L(M) = \bigcup_{q_f \in F} L_M(s, Q, q_f)$

where $s$ is the start state and $Q$ is all states.

Example

Simple Automaton

$q_0 \xrightarrow{a} q_1$, $q_1 \xrightarrow{b} q_0$, $q_1 \xrightarrow{c} q_1$

Start: $q_0$, Accepting: $\{q_1\}$

Computation

$L_M(q_0, \{q_0, q_1\}, q_1)$:

• Either go directly $q_0 \to q_1$ on $a$: contributes $a$
• Or go to $q_0$, loop, and exit: contributes $q_0 \xrightarrow{a} q_1 \xrightarrow{c} q_1 \xrightarrow{b} q_0 \xrightarrow{a} q_1$ pattern

Result (simplified): $a(c|ba)^*c^*|$ or via careful analysis: language of strings with more $a$‘s than $b$‘s modulo some pattern.

---

Summary

• Kleene’s theorem: regular expressions $\Leftrightarrow$ finite automata
• Regex to NFA: inductive construction using $\varepsilon$-transitions
• NFA to regex: region decomposition, eliminate states
• Regular = automata-recognisable = regex-definable