Reguläre Grammatik - [S] Informatiker

[dlite]

Hey,

da ich am Montag mündliche Prüfungen habe für mein Abitur sitze ich fest im Lernen. Ein Prüfungsthema beinhaltet die reguläre Grammatik, sprich rechts- und linksreguläre Sprachen.

Falls sich hier der ein oder andere Informatiker finden lässt, bitte ich um eine Erklärung, wie man von im untenstehenden Fall von der rechtsregulären Sprache eine äquivalente linksreguläre Sprache herleiten kann.

Fall: http://h11.abload.de/img/endlicherautomatosjd5.jpg
Ich habe versucht zum A^n B^n Problem einen Endlichen Automaten zu entwerfen, ebenso eine dazugehörigende rechtsreguläre Sprache. Ich habe aber, selbst nach stundenlangen Recherchen und etlichen Links von Unis usw. keine gute Erklärung gefunden, wie man nun diese linksreguläre Grammatik herleiten kann.

Falls sich jemand für solche theoretischen Sachen intressiert:
Ein Dank schonmal im Voraus für eure PM

[blackberry]

Studiere Mathe und nicht Info, habe mich jetzt aber trotzdem mal auf die Schnelle in das Thema eingelesen. Irrtum vorbehalten

Zunächst zum grundlegenden Verständnis:
Eine Grammatik heißt rechts-regulär, genau dann wenn alle ihre Produktionsregeln von der Form

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

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:

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

A --> B a

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:

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:

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:

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:

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:

S --> epsilon

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.

[dlite]

Hey, danke für diese Ausfürhliche Dokumentation

Für jemanden der sich damit nicht auskennt ists nicht weiter als Buchstabensalat, wenn man das Thema aber annähernd kennt ist es recht verständlich und auch einleuchtend geschrieben.


Rechtsregulär wäre nach dir jetzt: "Wenn im Zustand S -> Terminal a, dann gehe zu Zustand A"

Linksregulär demnach: "Gehe Zustand B wenn Zustand A und Terminal a"

Habe ich das jetzt richtig verstanden? Und woher hast du denn deine Informationen, ich hab nichts wirklich gutes gefunden außer solche Hardcore Mengenrechnungen

[blackberry]

Linksregulär demnach: "Gehe Zustand B wenn Zustand A und Terminal a"

So in der Art hatte ich das auch ursprünglich ganz am Anfang hingeschrieben, aber dann wieder gelöscht, weil ich mir gedacht habe, dass es vielleicht ein wenig irreführend klingen könnte. Der Grundgedanke ist aber richtig.

Willst du nun also aus einem solchen Automaten eine links-reguläre Grammatik generieren, so verfolgst du die Pfeile vom Endzustand (den du als Startsymbol in deiner links-regulären Grammatik betrachtest) rückwärts. Sagen wir also mal du bist im Zustand Z und zu Z führen n Pfeile aus den Zustanden A1,A2,...,An mit den Bedingungen t1,...,tn (also kommst du von Zustand A1 nach Z, wenn du in A1 bist und das Terminal t1 einliest usw.). Dann bildest du die Regel
Z --> (A1 t1) | (A2 t2) | ... | (An tn)
und betrachtest im Folgenden nun statt Z jeweils die Zustände A1,...,An und wiederholst das Verfahren für alle Pfeile, die zu diesen Zuständen gehen.

(ich hoffe mal, dass der Algorithmus in der Form auch schon völlig korrekt ist und es nicht irgendwelche exotischen Ausnahmen gibt, aber rein von der Überlegung her müsste das so funktionieren)

P.S.: Falls sich hier jemand wundert, weil die obige Produktionsregel nicht der von mir oben gegebenen Definition von links-regulär entspricht (ist weder vom Typ 1, 2, noch 3'). Dieses "verODERn" entspricht in Wirklichkeit einer Menge von Produktionsregeln, nämlich
1. Z --> (A1 t1)
2. Z --> (A2 t2)
...
n. Z --> (An tn)
Diese wiederum entsprechen dann obiger Definition. Man muss da also nicht zu pedantisch sein

Und woher hast du denn deine Informationen, ich hab nichts wirklich gutes gefunden außer solche Hardcore Mengenrechnungen

Aus "Hardcore Mengenrechnungen" ^^
Bin da in gewisser Weise durch mein Studium schon abgehärtet. Ist halt nur wichtig, dass man sich stets vor Augen führt, was die Notation eigentlich darstellen soll. Im Prinzip hat man ja immer diese Dualität zwischen mathematischem Modell und Realität. Wenn man dann nur noch das Modell betrachtet, dann sieht man am Ende halt nur noch Zeichen.

Viel was die Definitionen angeht habe ich mir schnell aus Wikipedia zusammengesucht (Grammatik, Produktionsregel, ...) und einiges auch aus ein paar Vorlesungsskripten zusammengelesen.

Ein ziemlich ausführliches wäre da wohl:
http://www.theory.informatik.uni-kas...ung/Skript.pdf
Satz 1.3.21 wäre da der Ausgangspunkt; dieser ist konstruktiv (vgl. Beweis). Satz 1.7.1 stellt mit der Äquivalenz von (1) und (2) den von dir gewünschten Zusammenhang her.

[dlite]

vielen dank.

Ich werds mir mal noch anschauen und in mich aufsaugen, denn im Vergleich zu den anderen Themen wie z.B. Schaltpläne oder diese Graphen ist dieser Kram mit regulärer Sprache noch das schwierigste