Reguläre Sprache

Definition

Eine Sprache $L\subseteq {\Sigma }^{\ast }$ heißt regulär, wenn es einen DEA $A$ gibt mit $L=L(A)$

Satz

Alle Endlichen Sprache sind regulär

Satz von Myhill und Nerode

Definition

Eine Sprache $L$ ist regulär genau dann, wenn Die Nerode-Rechtskongruenz ${\simeq }_L$ einen endlich Index hat.

Link to original

siehe auch:

• Abschlusseigenschaften der regulären Sprachen
• Nichtregularität einer Sprache
• Reguläre Ausdrücke