regulärer Ausdruck

reguläre Sprache $L$ $\iff$ regulärer Ausdruck α mit $L = L(\alpha)$ $\iff$ NEA $A$, der $L(\alpha)$ erkennt $\iff$ DEA $\tilde{A}$, der dieselbe Sprache wie $A$ erkennt

reguläre Ausdrucke

dabei $\varnothing$ - regulärer Ausdruck, der leere Menge beschreibt $\rightsquigarrow$ $L(\varnothing) = {}$