Direkt zum Inhalt

Lexikon der Mathematik: reguläre Sprache

manchmal auch reguläre Menge genannt, Sprache, zu der es einen sie definierenden regulären Ausdruck gibt.

Jede der folgenden Bedingungen ist äquivalent zur Regularität einer Sprache L:

Eine notwendige Bedingung für die Regularität einer Sprache liefert das Pumping-Lemma für reguläre Sprachen.

Wegen den genannten Beziehungen zu endlichen Automaten und einfachen Grammatiken werden reguläre Sprachen oft zur Definition von Bestandteilen von Programmiersprachen verwendet. Für die Definition kompletter Programmiersprachen sind sie selten verwendbar, weil diese häufig geklammerte Strukturen (Klammersprache) beinhalten, die grundsätzlich nicht regulär beschreibbar sind. Reguläre Sprachen charakterisieren wegen ihrer Beziehung zu endlichen Automaten auch das Verhalten vieler diskreter dynamischer Systeme.

  • Die Autoren
- Prof. Dr. Guido Walz

Schreiben Sie uns!

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.