Reguläre Sprache

Einführung

In der theoretischen Informatik ist eine reguläre Sprache oder reguläre Menge eine formale Sprache, die einigen Einschränkungen unterliegt. Reguläre Sprachen können von endlichen Automaten erkannt werden und von regulären Ausdrücken oder einer regulären Grammatik beschrieben werden.

Eine Sprache L über einem Alphabet Σ , also eine Menge von Wörtern L ⊆ Σ^∗, heißt dann regulär, wenn sie eine der folgenden äquivalenten Bedingungen erfüllt:

• L wird von einer regulären Grammatik erzeugt.

• L wird von einem endlichen Automaten akzeptiert.

• L kann durch einen regulären Ausdruck dargestellt werden.

Will man für eine gegebene Sprache nachweisen, dass sie regulär ist, so muss man sie demnach auf eine reguläre Grammatik, einen endlichen Automaten oder einen regulären Ausdruck zurückführen können.