Kleene's Theorem

Definition

Kleene’s Theorem establishes the equivalence between the class of languages recognizable by finite automata and the class of languages definable by regular expressions.

Statement

Given $L:{\Sigma }^{\ast }$, the following are equivalent:

1. $L=\mathcal{L}(e)$ for some Regular Expression $e$.
2. $L=\mathcal{L}(M)$ for some deterministic finite automata $M$.
3. $L=\mathcal{L}(N)$ for some non-deterministic finite automata $N$.

Proof