Übersetzerbau	WS 98/99 Heckmann Pape
5. Übungsblatt

 

Aufgabe 1 (1 + 2 + 3 Punkte)

1. Konstruiere den NEA zu dem regulären Ausdruck
   (a|b)* a b (a|b)*
2. Konstruiere einen zu diesem NEA äquivalenten DEA.
3. Minimiere den DEA aus Teil b.

Aufgabe 2 (2 + 2 + 1 Punkte)

Das folgende ist eine vereinfachte Beschreibung von Miranda-Stringkonstanten: Eine Stringkonstante bezeichnet eine (möglicherweise leere) Folge von Zeichen. Sie wird durch das Zeichen " eingeleitet und beendet. In der Zeichenfolge wird das newline-Zeichen als \n geschrieben, das Zeichen " als \" und das Zeichen \ selbst als \\. Legale Stringkonstanten sind also "hallo", "", "\\\"" und "n\n\"\\", aber nicht "\", """ oder "\\\".

1. Gib einen regulären Ausdruck über dem Alphabet {c, n, \, "} für die oben beschriebenen Stringkonstanten an. Das Zeichen c in diesem Alphabet soll für alle Zeichen außer n, \ und " stehen.
2. Gib einen DEA über demselben Alphabet für die oben beschriebenen Stringkonstanten an.
3. Minimiere den DEA aus Teil b.

Hinweis zu Aufgabe 2:
Der in Teil b. gesuchte NEA muß nicht unbedingt aus dem in Teil a. gesuchten regulären Ausdruck durch das in der Vorlesung beschriebene Verfahren abgeleitet werden, sondern kann auch einfach erraten werden. Wer also Schwierigkeiten hat, den regulären Ausdruck zu finden, kann also auch zuerst einen NEA suchen, um aus diesem auf einen geeigneten regulären Ausdruck zurückzuschließen. Für die Teilaufgabe c. soll dagegen wirklich das in der Vorlesung genannte Minimierungsverfahren angewandt werden.