Grammatik --> regulärer Ausdruck

Neue Frage »

weo Auf diesen Beitrag antworten »
Grammatik --> regulärer Ausdruck
Meine Frage:
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.
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.
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
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »