Studiere Mathe und nicht Info, habe mich jetzt aber trotzdem mal auf die Schnelle in das Thema eingelesen. Irrtum vorbehalten ![Wink](images/smilies/wink.png)
Zunächst zum grundlegenden Verständnis:
Eine Grammatik heißt rechts-regulär, genau dann wenn alle ihre Produktionsregeln von der Form
Code:
1. A --> epsilon, oder
2. A --> Terminal, oder
3. A --> Terminal Nichtterminal
sind (epsilon bezeichne das leere Wort). Eine Grammatik heißt links-regulär, genau dann wenn alle ihre Produktionsregeln von der Form 1., 2., oder 3'. sind, mit
Code:
3.' A --> Nichtterminal Terminal
Produktionsregeln der Form 1. und 2. sind im Prinzip uninteressant. Produktionsregeln vom Typ 1 dienen zum Abbruch der Wortgenerierung, Produktionsregeln vom Typ 2 fügen der Sprache nur einige Grundbausteine hinzu.
Regeln vom Typ 3 auf einen Automaten der die Grammatik akzeptieren soll entsprechen nun folgendem Ablauf:
Code:
A --> t B
"Bist du im Zustand A und liest das Terminal t, dann gehe in den Zustand B"
Eine solche Regel entspricht im Automaten also einem Zustandsübergang von A nach B unter der Bedingung t.
Der links-reguläre Fall ist im Prinzip die Umkehrung des rechts-regulären Falls. (dazu gleich mehr)
Das ganze kannst du dir auch nach diesem einfachen Prinzip klar machen: rechts-reguläre Sprachen wachsen nach rechts, links-reguläre Sprachen wachsen nach links. Dafür nehmen wir uns noch mal genau her, was eine Grammatik eigentlich ist.
Eine Grammatik ist ein 4-Tupel (Quadrupel) G = (V, Sigma, P, S), wobei V das Vokabular sei (Enthält Zeichen für Terminale und Nichtterminale), Sigma die Menge der Zeichen für Terminale, P die Menge der Produktionsregeln und S das Startsymbol (ein Nichtterminal).
Die zugehörige Sprache ist die Menge der durch G erzeugten Wörter. Dabei "erzeugt" G ein Wort, genau dann wenn man ausgehend vom Startsymbol durch Produktionsregeln S durch das Wort ersetzen kann.
Bei einer rechts-regulären Sprache ersetzen wir also im Startzustand durch ein leeres Wort (Typ 1), oder durch ein Terminal (Typ 2), oder durch ein Terminal plus ein Nichtterminal (Typ 3), wobei wir dieses Nichtterminal in weiteren Schritten auch durch Terminale mittels zugehörigen Produktionsregeln ersetzen müssen.
Nehmen wir mal die Produktionsregeln
1. S --> a S
2. S --> epsilon
Dann können wir im ersten Schritt S durch "a S" (Regel 1) ersetzen und dann im zweiten Schritt "a S" durch "aa S" (Regel 1) und dann im dritten Schritt durch "aa" (Regel 2). Wir könnten natürlich auch durch die Sequenz 1,2 das Wort "a" ableiten, oder durch 2 das leere Wort, oder durch 1,1,1,2 das Wort "aaa".
Dasselbe in der links-regulären Form:
1. S --> S a
2. S --> epsilon
Hier erhalten wir durch Regel 1 dann "S a", durch erneute Anwendung dann "S aa" und durch Regel 2 daraus "aa".
Rechts- und links-regulär sind also im Prinzip dasselbe, nur dass die Wörter eben einmal von links nach rechts hin wachsend (rechts-regulär) und einmal von rechts nach links hin wachsend (links-regulär) aufgebaut werden.
Zur Übersetzung:
Produktionsregeln der Form
können wir nun besser verstehen. Wir wissen, dass unser Automat in diesem Fall mit einem "a" aufgehört hat einzulesen. Nach dem "a" befinden wir uns somit im Endzustand. Wir haben also das Nichtterminal A durch "B a" ersetzt, d.h. wir haben den Endzustand A durch "B a" ersetzt, wobei dieses Nichtterminal B noch zu interpretieren wäre. Das Prinzip möchte ich nochmal an deinem Automaten erklären:
![](http://img6.imagebanana.com/img/a704t7db/sprache.png)
Hier wissen wir dann: wird ausgehend von B1 oder A2 ein "-" eingelesen (ich denke das bezeichnest du hier als Indikator dafür, dass der String hier endet), so ist der Automat im Endzustand.
Folglich gilt:
Code:
Z --> (B1 -) | (A2 -)
D.h. wir kommen in Z, wenn wir in B1 waren und ein Minus eingelesen wurde, oder in A2 waren und ein Minus eingelesen wurde.
Im Folgenden müssen wir noch klären, wie wir auf B1 bzw. A2 kommen können. Auch das machen wir entgegen der Pfeilrichtungen:
Code:
B1 --> A1 b
A2 --> B2 a
Dann haben wir noch nicht geklärt, wie wir in die Zustände A1 oder B2 kommen können. Auch das holen wir nach:
Code:
A1 --> (S a) | (B1 a)
B2 --> (S b) | (A2 b)
Wie kommen wir in S rein? Prinzipiell gar nicht, weil keine Pfeile auf S zeigen, die wir rückwärts laufen könnten. Also:
Nun setzen wir als neuen Startzustand Z statt S und du kannst dich leicht davon überzeugen, dass diese Regeln tatsächlich deine "abab..."/"baba..." Sprache produzieren.
Dann kann ich nur noch hoffen mich verständlich ausgedrückt zu haben und mich auch nirgendwo geirrt zu haben.