Grammatik --> regulärer Ausdruck |
03.07.2019, 12:47 | weo | Auf diesen Beitrag antworten » |
Grammatik --> regulärer Ausdruck Sei folgende Grammatik gegegen: S --> AB | ABC A --> abA | ab B --> x | y C --> xyC | y Nun ist ein äquivalenter regulärer Ausdruck zu finden, wie geh ich am besten vor? Meine Ideen: Mein Ansatz war a = (ab)*x|y.. also der Reihe nach die Möglichkeiten abschreiben nur wurde es dann schnell chaotisch, die Chomsky Normalform hätte ich sollte die es vereinfachen. |
||
03.07.2019, 14:20 | Elvis | Auf diesen Beitrag antworten » |
Gehört nicht zu einer formalen Grammatik etwas mehr Formalismus ? Wenn du schon mit Chaos anfängst, kann es nur noch chaotischer werden. |
||
03.07.2019, 16:13 | weo | Auf diesen Beitrag antworten » |
Terminale {a, b, x, y} Nicht Terminale {S, A, B, C} Startsymbol S Die Grammatik ist vom Typ 2, reguläre Ausdrücke beschreiben endliche Automaten also muss ich von der Chomsky-Normalform ausgehen. Ok, wie zauber ich daraus jetzt den Ausdruck? 1. jedes terminale was mit einem weiteren T oder NT steht bekommt eine neue Variable A->a, B->b, X->x S->AB | ABC A->ABA | AB B->x | y C->XYC | y _______________ 2. variablen mit 2+ auf rechten Seite werden ersetzt S -> AB | AT T -> BC A -> AG | AB G -> BA B -> x | y C -> XP | y P -> YC |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
|
Die Neuesten » |