Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Schöne Ferien!
 

 

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

+1 Punkt
68 Aufrufe

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?

 

Gefragt 25, Sep 2015 in 2008-H-03 von uafjv uafjv Tutor(in) (167,990 Punkte)  

Eine Antwort

0 Punkte
 
Beste Antwort

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;

Beantwortet 25, Sep 2015 von uafjv uafjv Tutor(in) (167,990 Punkte)  
...