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.