Teil 1

Es ergeben sich folgende reguläre Ausdrücke:

1. ´R_1 = ((((a+b)+c)^(**) * a) * ((a+b)+c)^(**))´
2. ´R_2 = (((b+c)^(**) * a) * (b+c)^(**))´
3. ´R_3 = ((((c^(**) * a) * (a+c)^(**)) * b) * ((a+b)+c)^(**))´

Es gilt dann:

´M(R_1) = {a, b, c}^(**) {a} {a, b, c}^(**)´ ´M(R_2) = {b, c}^(**) {a} {b, c}^(**)´ ´M(R_3) = {c}^(**) {a} {a, c}^(**) {b} {a, b, c}^(**)´

Wegen des Vorkommens von ´{a}´ in ´M(R_1)´ muss ein Wort aus ´M(R_1)´ mindestens ein ´a´ enthalten. Davor und dahinter können beliebige Wörter über ´{a,b,c}´ stehen, womit gesichert ist, dass mindestens ein ´a´ vorkommt (es können aber auch mehrere ´a´s vorkommen). Im Gegensatz zu ´M(R_1)´ können bei ´M(R_2)´ vor und hinter dem ´a´ nur Wörter über ´{b,c}´ stehen, die also kein weiteres ´a´ enthalten. Folglich enthält jedes Wort aus ´M(R_2)´ genau ein ´a´. Bei ´M(R_3)´ können vor dem ersten ´a´ nur ´c´s stehen, daher steht vor dem ersten ´a´ kein ´b´.

(Der angegebene Ausdruck geht davon aus, dass mindestens ein ´a´ und mindestens ein ´b´ vorkommen soll, da die Aufgabenstellung von einem ersten ´a´ bzw. ´b´ spricht. Sollte man davon ausgehen, dass dies nicht sein muss, so ist

´((((((c^(**) * a) * (a+c)^(**)) * b) * ((a+b)+c)^(**))+((c^(**) * a) * (a+c)^(**))) + c^(**))´

ein Ausdruck, der die Menge beschreibt.)

Teil 2

Die zum Ausdruck gehörende Menge ist ´M(R) = {a} {a,b,c}^(**) {c}´. In ´M(R)´ liegen also alle Wörter, die mit ´a´ beginnen und mit ´c´ aufhören. Somit sind die Wörter ´ac´, ´abc´, ´abcabc´ in ´M(R)´ und ´ab´ und ´bc´ nicht.