Kleines Nachschlagewerk Informatik
Reguläre Sprachen
Worum geht es?
Reguläre Sprachen sind die einfachste Art formaler Sprachen. Sie können durch endliche Automaten erkannt werden.

In den Ersetzungs- bzw. Produktionsregeln dürfen Nichtterminalsymbole nur durch ein Terminalsymbol oder eine Folge aus einem Terminal- und einem Nichtterminalsymbol ersetzt werden. Die Reihenfolge aus TS und NTS sollte hierbei innerhalb der Grammatik nicht verändert werden. Ebenso kann auf der rechten Seite das leere Wort stehen.

Zusammengefasst kann man die Ersetzungsregeln wie folgt schreiben:

      S --> a
      S --> Aa
      S --> ε
            


Es gibt auch Quellen, welche die Ersetzungsregeln so formulieren, dass ein NTS nur durch eine Kombination von NTS und TS oder das leere Element ε ersetzt werden darf. Das ist jedoch identisch mit obiger Vorgabe.
Links- und rechtsreguläre Grammatiken
Eben wurde festgestellt, dass man die Reihenfolge TS-NTS bei den Ersetzungsregeln innerhalb einer Definition nicht ändern soll. Legt man sich so fest, dass das NTS immer links steht, spricht man von einer linksregulären Grammatik. Steht das NTS rechts, so spricht man von einer rechtsregulären Grammatik.

Linksreguläre Wörter entstehen somit von rechts nach links, weil immer links ersetzt wird. Bei rechtsregulären ist es umgekehrt. Weil Menschen in Mitteleuropa von links nach rechts schreiben, ist die rechtsreguläre Grammatik die gebräuchlichere. Spricht man also von regulären Grammatiken, meint man oft eine rechtsreguläre.
Beispiel einer regulären Sprache
Als Beispiel soll wieder die ganze Zahl Verwendung finden. Es wird eine rechtsreguläre Grammatik verwendet. Dieses Beispiel sieht recht kompliziert aus, aber es sollte auf ε verzichtet werden und Zahlen können, müssen aber kein Vorzeichen haben.

Grammatik (Produktionsregeln)

      S --> +Z
      S --> -Z
      S --> 0..9
      S --> 1..9R
      R --> 0..9
      R --> 0..9R
      Z --> 1..9
      Z --> 1..9R
            
Hier sollen Einige Zahlen mit den grammatikalischen Regeln getestet werden. Man wendet die Produktionsregeln einfach rückwärts an, ein Probieren bei mehreren Möglichkeiten ist notwendig. Ein baumförmiges Aufschreiben hat sich bewährt. Ein Wort gehört zu einer Sprache, wenn das Startsymbol erreicht wird und keine Zeichen mehr übrig sind. Bei den ersten beiden Zahlen klappt das gut. Die dritte hat eine führende Null, das Startsymbol kann nicht erreicht werden. Im letzten Beispiel wird der Startzustand erreicht und kann nicht erneut mit S ersetzt werden. Somit bleiben Zeichen übrig.



Von der Grammatik zum Automaten
Von einer Grammatik kommt man recht einfach zum erkennenden Automaten. Es gibt zwei Wege, die vorgeschlagen werden. Beiden gemein ist, dass die Terminalsymbole das Alphabet und die Nichtterminalsymbole die Zustände bilden. Jede Bildungsregel wird als Übergang gelesen.

Der erste Weg eignet sich für linksreguläre Grammatiken, wenn die Zeichen von links nach rechts gelesen werden. Dabei ist das Startsymbol der Grammatik (S) der Endzustand des Automaten. Das heißt, dass die Regel A-->Ba so gelesen wird, dass das Zeichen a einen Zustandswechsel von B nach A ausführt. Vom Startzustand führen die Regeln zu anderen Zuständen, die nur Terminalsymbole haben.

Als Beispiel für eine linksreguläre Grammatik sollen die Smileys :-) :) :-( und :( verwendet werden.

      S --> A)
      S --> A(
      A --> :
      A --> B-
      B --> :
            




Der zweite Weg eignet sich, wenn ebenfalls von links gelesen wird, die Grammatik aber rechtsregulär ist. Basis ist obiges Beispiel ganzer Zahlen mit Vorzeichen. Hierbei beginnt man mit dem Startsymbol als Startzustand und verzweigt auf die Folgezustände. Final sind die Zustände, für welche die Ersetzungsregel nur Terminalsymbole vorsieht. S-->aB bedeutet also, dass a den Wechsel von S zu B erzwingt. Im Bild steht die 0 wieder für die Ziffern 0 bis 9, die 1 für die Ziffern 1 bis 9.





In fast jedem Fall jedoch ergeben sich nichtdeterministische Automaten. Diese lassen sich jedoch in deterministische Automaten umwandeln. Wie dies geht, steht im Kapitel über endliche chapter_0050.html .