Ableitung von (a+b)*b(ba+b) mit der Grammatik der Musterlösung?

Question

Ich versuche gerade die Musterlösung nachzuvollziehen, da sie mir "zu simpel" ist. Habe mir dafür als Testwort den regulären Ausdruck aus Aufgabe 1 genommen:

(a+b)*b(ba+b)

Könnte jemand vielleicht den Ausdruck mit der Grammatik aus der Musterlösung ableiten?

 

Answer 1

Hallo,

Ihr regulärer Ausdruck kann so nicht abgeleitet werden, weil es strenggenommen kein regulärer Ausdruck ist. Sie haben einige Abkürzungen eingebaut (Und zwar durch das Weglassen von Klammern), die wir zwar zulassen, weil wir verstehen, was gemeint ist, die aber durch die Grammatik nicht abgedeckt werden.

Wenn man entsprechende Klammern hinzufügt, erhält man (bspw.) folgenden korrekten regulären Ausdruck:

(((a+b)*b)((ba)+b))

Diesen kann man entsprechend dem folgenden Ableitungsbaum erzeugen:

Viele Grüße

Lukas König

PS. Wenn Sie das im Info-II-Generator nachvollziehen möchten, können Sie dieses Skript verwenden (Klammern sind als geschweifte Klammern dargestellt, da "(", ")" im Programm schon anderweitig vergeben sind):

grammar parse({, {,{, a, +, b, }, *, b,}, {, {, b, a, }, +, b, },})--0: S: a,b,c, +, x, *, {, }, O: S:
S => {, S, +, S, };
S => {, S, x, S, };
S => {, S, S, };
S => S, *;
S => c;
S => b;
S => a;
S => O;