Übung zur Vorlesung

Theoretische Informatik I

Prof. Christoph Kreitz / Jens Otten Universität Potsdam, Theoretische Informatik — Sommersemester 2004 Blatt 8 — Abgabetermin: 19. Juni 2004, 11.00 Uhr

Quiz 8

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

[ ] Falls die Sprache L regulär ist, dann ist auch L^{m}:={w^{m} | w∈L} für m∈IN regulär. [ ] Falls L regulär ist, dann ist auch die Sprache L^{m}∘L^{m} regulär. [ ] Seien A_{1} und A_{2} zwei DEAs mit n_{1} und n_{2} Zuständen. Dann gibt es einen DEA mit n_{1}+n_{2} Zuständen, der die Sprache L:=L(A_{1})∘L(A_{2}) akzeptiert.

[ ] Für jede reguläre Sprache L gibt es genau einen minimalen regulären Ausdruck R mit L=L(R).

[ ] Die Minimierung eines NEA mit Hilfe des Table-filling Verfahrens erzeugt einen minimalen NEA.

Aufgabe 8.1 (Abschlusseigenschaften regulärer Sprachen) Zeigen Sie, dass die regulären Sprachen bezüglich der folgenden Operationen abgeschlossen sind:

1. min(L):={w | w∈L und kein echter Präfix von w ist in L enthalten }.

2. max(L):={w | w∈L und für alle Wörter x≠ϵ gilt wx∉L}.

3. init(L):={w | für ein Wort x≠ϵ gilt wx∈L}.

4. quot(a, L):={w | aw∈L} für ein Symbol a.

Tipp: Beginnen Sie mit einem DEA für die Sprache L und konstruieren Sie daraus einen Automaten für die gewünschte Sprache.

Aufgabe 8.2 (Minimierung von DEAs) Gegeben sei der durch die folgende Übergangstabelle definierte DEA.

0 1
→ A B E
B C F
∗C D H
D E H
E F I
∗F G B
G H B
H I C
∗I A E

1. Ermitteln Sie mit Hilfe des Table-filling Verfahrens alle Paare äquivalenter Zustände.

2. Geben Sie einen äquivalenten minimalen DEA an.

Übung zur Vorlesung Theoretische Informatik I Blatt 8

Aufgabe 8.3 (Eigenschaften regulärer Sprachen) [3 Punkte]

Die in Aufgabe 8.1 unter 4. vorgestellte Funktion quot(a, L) wird auch als ”Ableitung” betrachtet und mit \frac{dL}{da} dargestellt. Wenn R ein regulärer Ausdruck ist, dann soll \frac{dR}{da} dasselbe bedeuten wie \frac{dL}{da} mit L=L(R). So gilt z.B. \frac{d(R+S)}{da}=\frac{dR}{da} + \frac{dS}{da}.

1. Formulieren Sie die Regel für die Ableitung \frac{d(RS)}{da}.

2. Formulieren Sie die Regel für die Ableitung \frac{d(R^{∗})}{da}.

3. Verwenden Sie die drei Ableitungsregeln, um die Ableitung für den regulären Ausdruck (0 + 1)^{∗}110 in Bezug auf 0 und 1 zu berechnen.

Aufgabe 8.4 (Minimierung von DEAs) [3 Punkte]

Gegeben sei der durch die folgende Übergangstabelle definierte DEA.

0 1
∗A D B
→ ∗B C A
C B F
D A E
E F D
F E C
G F D

1. Ermitteln Sie mit Hilfe des Table-filling Verfahrens alle Paare äquivalenter Zustände.

2. Geben Sie einen äquivalenten minimalen DEA an.

Aufgabe 8.5 (Abschlusseigenschaften von Sprachen) [3 Punkte]

1. Sei w_{1}=a_{0}a_{0}a_{1} und w_{i}=w_{i−1}w_{i−1}a_{i} für i>1. Es ist z.B. w_{2}=a_{0}a_{0}a_{1}a_{0}a_{0}a_{1}a_{2}. Sei L_{n}={w_{n}}, d.h. die Sprache, die aus der Zeichenreihe w_{n} besteht. Dann ist der kürzeste reguläre Ausdruck für L_{n} die Zeichenreihe w_{n} selbst, und die Länge dieses Ausdrucks ist 2^{n+1}−1. Geben Sie n reguläre Ausdrücke der maximalen Länge kn (für ein festes k∈IN) an, deren Schnittmenge die Sprache L_{n} beschreibt.

2. Sei L eine beliebige Sprache über dem Alphabet {0}. Beweisen Sie, dass L^{∗} regulär ist. Tipp: Betrachten Sie z.B. L_{p}={0^{i} | i ist eine Primzahl}. Dann ist die Sprache L_{p}^{∗}={w | w=ϵ oder w=00v mit v∈{0}^{∗}} regulä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.