Compilerbau

Musterlösung
2. Übungsaufgabe (40 Punkte)

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)^*
      Die Sprache von der linken RA beinhalten auch \epsilon. Alle Elemente im rechten RA müssen mit einem R beginnen, was nur dann \epsilon enthält, wenn es Element von L(R) ist. Also gilt die Gleichung nicht.
   2. (4 Punkte) ST /= TS.
      Angenommen, ST = TS. Seien S = s, T = t, damit ist L(ST)={st} und L(TS)={ts}, und L(ST) /= L(TS) im Widerspruch zur Annahme. Damit ist ST /= TS.
   3. (4 Punkte) (R^*|S^*) /= (R|S)^*.
      Angenommen, (R^*|S^*) = (R|S)^*. Seien R = r, S = s. rsrs \element L((R|S)^*), aber nicht \element (R^*|S^*), im Widerspruch zur Annahme. Damit ist die Aussage wahr.
2. (4 Punkte) Sei R = (ab|b)^*c. Welche der Zeichenreihen sind in L(R)? Warum?
   1. abbbabc
      ab - b - b - ab - c ok
   2. c
      \epsilon - c ok
   3. babac
      b - ab - x nichts passt auf a, nicht in L(R)
   4. abab
      ab - ab - x kein c, nicht in L(R)
3. (4 Punkte) Sei R = ab^*c (a|b) c. Welche der Zeichenreihen sind in L(R)? Warum?
   1. acac
      a - \epsilon - c - a - c ok
   2. acbabbc
      a - \epsilon - c - b - x nichts für a, nicht in L(R)
   3. cabac
      fängt nicht mit a an, nicht in L(R)
   4. abcc
      a - b - c - kein a oder b, nicht in L(R)
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.
   a | (a(a|b)^*a)
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. ((a | b)³)^* (mehrere Varianten)
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. 1^*01^*01^*01^*01^*
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. (1^*011^*)^*

(i) Es gilt: (S|T)* = (S* | T*)*
L((S*|T*)*) Teilmenge von L((S*T*)*) gdw.
L((S+ | epsilon | T+ | epsilon)*) Teilmenge von L(((S+ | epsilon) (T+ | epsilon))*) gdw.
L((S+ | T+ | epsilon)*) Teilmenge von L(((S+T+ | S+ epsilon | epsilon T+ | epsilon epsilon)*) gdw.
L((S+ | T+ | epsilon)*) Teilmenge von L(((S+T+ | S+ | T+ | epsilon epsilon)*) q.e.d.

(ii) Es sei T ein RA, dann gilt (TT)* Teilmenge T*
L((S*T*)*) Teilmenge L(((S*|T*)(S*|T*))*) Teilmenge L((S*|T*)*) gdw. L((S*T*)*) Teilmenge L((S*S* | S*T* | T*S* | T*T*)*) Teilmenge L((S*|T*)*) gdw. q.e.d.

Da gezeigt wurde, daß L((S|T)*) = L((S*T*)*) ist auch (S|T)* = (S*T*)*.