Nicht-reguläre Sprachen

Diejenigen Sprachen, die sich mit endlichen Automaten beschreiben lassen, heißen reguläre Sprachen.

Ein Beispiel für eine Sprache, die nicht regulär ist, die die Menge aller geklammerten Terme. Sie lässt sich beispielsweise durch die Grammatik G = (V, A, P, S) beschreiben mit

der Menge der Nichtterminale V = { Buchstabe, Bezeichner, Operator, Term }
dem Alphabet A = {"a", …, "z", "*", "/", "+", "-", "(", ")"}
dem Startsymbol S = Term
und den Produktionsregeln

R1: Buchstabe = "a" | "b" | ... | "z"
R2: Bezeichner = Buchstabe { Buchstabe }
R3: Operator = "+" | "-" | "*" | "/"
R4: Term = Bezeichner | Term Operator Term | "(" Term ")"

Die Regel R4 stellt sicher, dass der Term genausoviele öffnende wie schließende Klammern enthält und diese jeweils paarweise in der richtigen Reihenfolge einen Term umfassen. Dadurch sind Worte wie

5 + ) 3 + 4 (
( (3 + 4) ) )
2 + ( ( 4 - 7 )

ausgeschlossen.

Warum gibt es keinen DEA, der die Sprache der geklammerten Terme beschreibt?

Versuchen Sie doch einfach, einen zu erstellen! So wird Ihnen am einfachsten bewusst, wo das Problem liegt. Am besten sehen Sie sich anschließend Abbildung 4 auf Seite 41 des Schulbuches "Informatik 7 (gA)" an und lesen den Text daneben.

Weitere Beispiele nicht-regulärer Sprachen

alle Wörter über dem Alphabet A = {a, b}, die genausoviele a's wie b's enthalten.
die Programmiersprachen Java, C, Pascal usw. (wegen geklammerten Termen, Schachtelungsebenen von Scopes usw.)