Compilerbau

2. Übungsaufgabe (40 Punkte)

Datum: MO 20.4. / DO 23.4.

Abgabetermin: MO 27.4. / DO 30.4.

Lernziel: Reguläre Ausdrücke auswerten und formulieren können

1. Beweisen bzw. widerlegen Sie die folgenden Gleichungen für reguläre Ausdrücke R, S, und T:
   1. (4 Punkte) (RS | R)^* = R(SR | R)^*
   2. (4 Punkte) ST /= TS.
   3. (4 Punkte) (R^*|S^*) /= (R|S)^*.
2. (4 Punkte) Sei R = (ab|b)^*c. Welche der Zeichenreihen sind in L(R)? Warum?
   1. abbbabc
   2. c
   3. babac
   4. abab
3. (4 Punkte) Sei R = ab^*c (a|b) c. Welche der Zeichenreihen sind in L(R)? Warum?
   1. acac
   2. acbabbc
   3. cabac
   4. abcc
4. (5 Punkte) Sei \Sigma = { a, b }. Geben Sie eine reguläre Ausdruck an, dessen Sprache alle Zeichenreihen enthält, die mit einem a anfangen und aufhören.
5. (5 Punkte) Sei \Sigma = { a, b }. Geben Sie eine reguläre Ausdruck an, dessen Sprache alle Zeichenreihen enthält, dessen Länge ein vielfaches von 3 sind.
6. (5 Punkte) Sei \Sigma = { 0, 1 }. Geben Sie eine reguläre Ausdruck an, dessen Sprache alle Zeichenreihen enthält, die genau vier Nullen haben.
7. (5 Punkte) Sei \Sigma = { 0, 1 }. Geben Sie eine reguläre Ausdruck an, dessen Sprache alle Zeichenreihen enthält, in dem jeder 0 durch mindestens einer 1 gefolgt wird.