Übung zur Vorlesung

Theoretische Informatik I

Prof. Christoph Kreitz / Jens Otten Universität Potsdam, Theoretische Informatik — Sommersemester 2004 Blatt 5 — Abgabetermin: 22. Mai 2004, 11.00 Uhr

Quiz 5

Markieren Sie die nachfolgenden Aussagen als ”wahr” oder ”falsch”.

[ ] Es gibt genau zwei Sprachen L, deren Kleene’sche Hülle L^{∗} endlich ist. [ ] Der reguläre Ausdruck (0 + 10)^{∗} beschreibt genau die Zeichenreihen über dem Alphabet {0, 1}, bei denen hinter einer Eins immer eine Null stehen muss.

[ ] Für jeden regulären Ausdruck R gibt es einen DEA A mit L(R) = L(A). [ ] Die folgende Äquivalenz gilt: L(ϵ + (a + b)^{+}) = L(((a + b)(a + b)^{∗})^{∗}). [ ] Die folgenden regulären Ausdrücke sind äquivalent: R + (ST) und RS + RT.

Aufgabe 5.1 (Reguläre Ausdrücke; Umwandlung in ϵ-NEA)

Geben Sie reguläre Ausdrücke für die folgenden Sprachen an:

1. Die Menge der Zeichenreihen über dem Alphabet {a, b, c}, die mindestens ein a und mindestens ein b enthalten.

2. Die Menge der Zeichenreihen über dem Alphabet {a, b, c}, deren zweites Zeichen ein a und deren drittletztes Zeichen ein c. (Das drittletzte Zeichen ist das dritte Zeichen vor dem Ende der Zeichenreihe.)

3. Die Menge der Zeichenreihen über dem Alphabet {0, 1}, deren Anzahl von Nullen durch 3 teilbar ist. Beachten Sie, dass die Zahl Null durch 3 teilbar ist.

Geben Sie einen endlichen Automaten für mindestens eine dieser Sprachen an. Benutzen Sie die in der Vorlesung vorgestellte Konstruktion zur Umwandlung eines regulären Ausdrucks in einen ϵ-NEA.

Aufgabe 5.2 (Äquivalenz von regulären Ausdrücken)

Zeigen oder widerlegen Sie die Gültigkeit der folgenden Äquivalenzen (für beliebige reguläre Ausdrücke R und S):

1. (R + S) + R = S + R

2. (R + S)^{∗} = R^{∗} + S^{∗} Übung zur Vorlesung Theoretische Informatik I Blatt 5

Aufgabe 5.3 (Praktische Anwendungen regulärer Ausdrücke) [3 Punkte]

Sie wollen im Internet nach preisgünstigen Musterlösung zu den Hausaufgaben für ”Theoretische Informatik I” suchen. Dazu müssen Sie einen regulären Ausdruck konstruieren, der Ihnen passende Textmuster erkennt. Ein solches Textmuster wäre zum Beispiel

”TI1 Lösungen zu den Hausaufgaben (außer Aufgabe 5.3) für nur 12.50 ”

Es reicht aus Textmuster zu erkennen, die mit ”TI1” beginnen und mit einem Preis enden. Preise können z.B. die folgende Form haben: 5 , 0.99 , 9.– , 7, 1.–, 9.99.

Geben Sie einen entsprechenden regulären Ausdruck an, der diese Textmuster beschreibt. Für den regulären Ausdruck (0+1+2+3+4+5+6+7+8+9) können Sie die abkürzende Schreibweise [0-9] verwenden. Entsprechend können Sie Groß- bzw. Kleinbuchstaben (inklusive der Sonderzeichen) mit [A-Z] bzw. [a-z] abkürzen.

Aufgabe 5.4 (Reguläre Ausdrücke; Umwandlung in ϵ-NEA) [3 Punkte]

Geben Sie reguläre Ausdrücke für die folgenden Sprachen an:

1. Die Menge der Zeichenreihen über dem Alphabet {0, 1}, die mindestens ein Paar aufeinanderfolgende Nullen oder ein Paar aufeinanderfolgende Einsen enthalten.

2. Die Menge der Zeichenreihen über dem Alphabet {a, b, c}, die maximal dreimal hintereinander das Symbol a enthalten.

3. Die Menge der Zeichenreihen über dem Alphabet {0, 1}, die die Teilzeichenreihe 010 nicht enthalten.

Geben Sie einen endlichen Automaten für eine dieser Sprachen an. Benutzen Sie die in der Vorlesung vorgestellte Konstruktion zur Umwandlung eines regulären Ausdrucks in einen ϵ-NEA.

Aufgabe 5.5 (Äquivalenz von regulären Ausdrücken) [3 Punkte]

Zeigen oder widerlegen Sie die Gültigkeit der folgenden Äquivalenzen (für beliebige reguläre Ausdrücke R und S):

1. (R + S)^{∗}S = (R^{∗}S)^{∗}

2. (RS + R)^{∗}R = R(SR + R)^{∗}

Haben Sie Fragen, Anregungen oder Probleme? Lassen Sie es uns wissen!

• Prof. Christoph Kreitz, Raum 1.18, kreitz@cs.uni-potsdam.de, Tel. 0331/977 3060 Sprechstunde: immer, wenn die Türe des Raumes 1.18 offen steht, und am Mittwoch 11.00 bis 12.30 Uhr

• Jens Otten, Raum 1.20, jeotten@cs.uni-potsdam.de, Tel. 0331/977 3072 Sprechstunde: immer, wenn die Türe des Raumes 1.20 offen steht, und am Dienstag 14.00 bis 16.00 Uhr.