Big Result

Any Language created from a:

• Regular Expression
• Deterministic Finite Automaton
• Non-Deterministic Finite Automaton can be rewritten in each other’s form.

Formal Definition

Let $L$ be a Language, then the following are equivalent:

1. $L=\mathcal{L}(R)$ for some Regex $R$
2. $L=\mathcal{L}(M)$ for some DFSA $M$
3. $L=\mathcal{L}(M)$ for some NFSA $M$