Lange ist der letzte Artikel zum Thema „Formale Sprachen“ her, deshalb möchte ich heute zeigen, wie man ε-Regeln aus Grammatiken entfernt. Warum sollte man das überhaupt tun? Nun ja, ε-Regeln verstoßen gegen die Längenmonotonie, die wiederrum für kontextfreie, kontextsensitive als auch reguläre Grammatiken gefordert ist. Die Längenmonotonie besagt, dass in P, also den Produktionsregeln, die rechte Seite mindestens genau so lang sein muss wie die linke. Formal ausgedrückt also |α| ≤ |β|. Da nun mal |α| > 0 ist und |ε| = 0 müssen ε-Regeln entsprechend für Typ 1-3 der Chomsky-Hierarchie entfernt werden.
Beispiel ε-Regeln entfernen
Gegeben sei folgende Grammatik (N,T, P, s) G = ({S, A, C}, {a, c}, {S → aA, A → cA | C, C → a | ε}, S)Zu Beginn sind die Nicht-Terminale gesucht, die sich bis zu einem ε problemlos ableiten lassen. Bei der Regel C → a | ε lässt sich gut erkennen, dass eine Ableitung auf das leere Wort direkt möglich ist. Bei der zweiten Regel A → cB | C ist zu sehen, dass A sich auf C ableiten lässt und C sich wiederrum zum leeren Wort – also wieder eine Möglichkeit gefunden, zum ε zu gelangen. Und so auch die erste Regel S → aA, da dort wieder das Nicht-Terminal A auftaucht, was über C zum leeren Wort ableitbar ist. Das war der erste Schritt, die Menge M = {S, A, C} zu bilden.
Jetzt geht es an das Umformulieren der Regeln. Dazu schreibe ich nochmal alle übersichtlich untereinander:
- S → aA
- A → cA | C
- C → a | ε
ε-Regel entfernt, sehen die Produktionsregeln, wie folgt aus:
- S → aA
- A → cA | C
- C → a
Transformation des Regelwerkes
Jetzt muss natürlich sichergestellt sein, dass die ursprüngliche Grammatik die gleichen Wörter erzeugen kann, wie die Grammatik ohne die Regel C → ε. Um das sicherzustellen, schaut man nach den Nicht-Terminalen die sich in M befinden, also S, A und C. Wo auch immer S, A und C nun auf der rechten Seite der Produktionsregeln auftaucht, müssen Abkürzungsregeln gebildet werden.
Hier sei gesagt, es müssen nicht immer alle Nicht-Terminale vorkommen. Es hätte auch nur S und A sein können in einem anderen Beispiel.
Die Abkürzungsregeln bildet man, indem man sich S → aA als erste Regel anschaut. A ist hier das Nicht-Terminal aus der Menge M. Jetzt lässt man an der Stelle das A als Nicht-Terminal weg und damit hat man die Regel schon abgekürzt, da sich nun S direkt auf das Wort a ableiten lässt. Das sieht dann so aus:
S → aA | a
So geht es auch weiter mit der zweiten Regel A → cA | C. Hier kommen A und C als Nicht-Terminale vor. Die erste Kombination ist cA, lässt man das A weg bleibt nur noch c übrig. Das kann jetzt auch an die bestehende Regel drangehangen werden, natürlich wieder als oder-Verknüpfung. Kürzer kann man die Regel nicht machen.
- A → cA | C | c
Als letzte Regel bleibt nur noch C → a. Bei dieser Regel wurde schon das ε entfernt und kürzer kann die Regel auch nicht mehr umgeschrieben werden, also bleibt sie wie sie ist
- C → a
So sehen jeztzt die Produktionsregeln P der Grammatik G aus, nachdem das ε entfernt wurde
- S → aA | a
- A → cA | C | c
- C → a
Wie hier jetzt auch sehr gut zu sehen ist, wird die anfangs angesprochene Längenmonotonie eingehalten: Die rechte Seite ist mindestens genau so lang, wie die linke Seite.
Ein weiteres kleines Beispiel
Nochmal eine weitere Produktionsregel, die wesentlich komplexer ist, als im obigen Beispiel:
Gegeben ist die Menge M = {B, C} mit den Nicht-Terminalen, die sich auf ein ε ableiten lassen und die folgende Produktionsregel einer weiteren Grammatik G‘. Wie würde man diese nun transformieren?
A → bbB | ABCa
Betrachtet werden wieder die Nicht-Terminale auf der rechten Seite. A → bbB ist der erste Teil. Hier lässt man das B einfach weg, wie gehabt und hängt das Überbleibsel als oder-Verknüpfung an die ursprüngliche Regel hinten dran (An welcher Stelle das bb platziert wird, spielt hier keine Rolle):
A → bbB | bb | ABCa
Weiter geht’s mit dem schwierigerem Teil, A → ABCa:
Nicht-Terminale wieder beachten, die Bestandteil der Menge M sind. Also, den Nicht-Terminalen, die auf ε abgeleitet werden können. So sieht die abschließende Regel, wie folgt aus:
A → bbB | bb | ABCa | ABa | ACa | Aa
Es wird bei der Transformation alle Varianten ergänzt, in dem man ein oder eben beide Nicht-Terminale der Menge M in der Regel weglässt bzw. hinten anfügt. A bleibt deshalb immer bestehen, da es eben nicht in M enthalten ist und nicht ableitbar auf ε ist
Ausblick
Ich hoffe, die Erklärung, wie man denn jetzt eine Grammatik von ε-Regeln befreit, hat euch in irgendeiner Form weitergeholfen. Es mag am Anfang etwas Wirr und unverständlich wirken, aber nach 1-2 Lesen des Posts, kommt sicherlich der AHA-Effekt. Falls aber doch wer nicht ganz weiterkommen sollte, schreibt gerne in die Kommentare und wir versuchen gemeinsam einen Weg zu finden.
In den kommenden Posts rund um die theoretische Informatik möchte ich mich den Themen rund um Compiler, Interpreter, Scanner und Parser widmen. Dabei sieht man dann gut, wieso formale Sprachen so wichtig für die Informatik sind. Natürlich werden aber auch die Unterschiede der Begriffe beleuchtet. Bis zum nächsten Mal!
Start the discussion