1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Einführung in Berechenbarkeit, Formale Sprachen und Komplexitätstheorie Wintersemester

1

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und Komplexität

Einführung in Berechenbarkeit, Formale Sprachen und Komplexitätstheorie

Wintersemester 2005/200625.10.2005

1. Zentralübung

Christian Schindelhauer

Berechenbarkeit, Formale Sprachen, Komplexitätstheorie 01-2


Algorithmen und KomplexitätChristian Schindelhauer

Aufgabe 6

Seien L1 und L2 regulär. Beweisen Sie, dass auch L1\L2 regulär sind.

Strategie: Beweis folgt aus– Lemma A

• Sei L regulär. Dann ist auch *\L regulär.– Lemma B

• Seien L1 und L2 regulär. Dann ist auch L1L2 regulär.

weil L1\L2 = L1 (*\L2 )




Aufgabe 6

Lemma A – Sei L regulär. Dann ist auch *\L regulär.

Beweis:

– Betrachte DFA M = (Q, , , q0, F)

– Konstruiere M’ = (Q, , , q0, Q\F)

– Behauptung L(M’) = *\L.– Beweis:

• Nach Abarbeiten von w ist Maschine M und M’ im selben Zustand

• Wegen der Invertierung der akzeptieren Zustände gilt: M akzeptiert w genau dann, wenn M’ akzeptiert nicht w.

– QED.




Aufgabe 6

Lemma B

– Seien L1 und L2 regulär. Dann ist auch L1L2 regulär.Beweis

– Es gilt:

– wobei

– Da das Komplement und die Vereinigung einer regulären Sprache regulär sind, folgt das Lemma.




Aufgabe 1

Gesucht: DFA für

Betrachte:– A = * 010 *

Automat ergibt sich aus der Konkatenation der Automaten für *, 0, 1, 0, *

NFA für A (-Übergänge schon ersetzt)




NFA für A = * 010 *

Potenzmengenkonstruktion liefert DFA

Zustand {1,2,4} , {1,4}, {1,3,4} können zusammengefasst werden zu q

Invertierung der akzeptierenden und nicht akzeptierenden Zustände ergibt




Aufgabe 5

Falls L regulär ist, dann ist es auch

2 Lösungsmöglichkeiten:– NFA N aus DFA M konstruieren

• Im DFA M für L alle Übergänge umdrehen• Startzustand zum einzigen akzeptierenden Zustand machen• Neuer Startzustand in N mit -Übergang zu akzeptierenden

Zuständen von M– Beweis über reguläre Ausdrücke

• Zu jedem regulären Ausdruck R einen Ausdruck Rrev gibt, der Lrev beschreibt

• Korrektheit durch Induktion über dem Aufbau




Aufgabe 5: 1. Lösungsansatz

Gegeben sei ein DFA M = (Q, , , q0, F) mit L(M) = L

Definiere NFA N = (Q {q’}, , ’, q’, {q0}) wie folgt:

–Für q≠q’: ’(q, ) = –Für q≠q’ gilt für a

’(q’, ) = F–Für a : ’(q’, a) =

Angenommen M akzeptiert w= w0w1w2 ... wn

–Sei q0q1q2 ... qn, so dass für alle i {1,...,n}: (qi,wi+1)=qi+1

–Dann ist qn FBetrachte die Folge q’ qn ... q2q1q0

–Dann ist qi ’(qi+1,wi+1)–Außerdem: ’(q’, ) = qn –und q0 ist der akzeptierende Zustand

Also akzeptiert N das Wort wn ... w2w1

Angenommen N akzeptiert das Wort wn ... w2w1

– Dann gibt es eine Folge q’qn ... q2q1q0

– wobei ’(q’, ) = qn und qn F

– und qi ’(qi+1,wi+1) für alle i {1,...,n}

– Dann ist (qi,wi+1)=qi+1

– Betrachte die Folge q0q1q2 ... qn

– Auf dieser folge führt M eine akzeptierende Berechnung für w durch

Also akzeptiert M das Wortw= w0w1w2 ... wn




Aufgabe 5: 2. Lösungsansatz

Behauptung: – Für jeden regulären Ausdruck A gibt es einen regulären Ausdruck

der die Sprache L(A)rev beschreibt. Beweis:

1. Fall A = Dann sei Arev = 2. Fall A= Ø Dann sei Arev = Ø3. Fall A = (R1 R2) Dann sei Arev = (R1

rev R2rev)

4. Fall A = (R1 R2) Dann sei Arev = (R2rev

R1rev)

5. Fall A = (R1)* Dann sei Arev = (R1rev)*

1. Korrektheit folgt über Indunktion über den Aufbau des regulären Ausdrucks

2. Für jeden Fall lässt sich die Korrektheit leicht nachvollziehen.




Aufgabe 4

1. M1 = ({0,1,...,6}, {0,1,...,9}, , 0, {4}) Für alle q {0,1,...,6}, a {0,1,...,9}: (q,a) = 10 q + a mod 7

2. M2= ({0,1,...,6}, {0,1}, , 0, {4})

1. Für alle q {0,1,...,6}, a {0,1}: (q,a) = 2 q + a mod 7

Zur Anzeige wird der QuickTime™ Dekompressor „TIFF (LZW)“

benötigt.

11


Algorithmen und Komplexität

Heinz Nixdorf Institut& Institut für InformatikUniversität PaderbornFürstenallee 1133102 Paderborn

Tel.: 0 52 51/60 66 92Fax: 0 52 51/60 64 82E-Mail: [email protected]://www.upb.de/cs/schindel.html

Vielen DankEnde der 1. ZentralübungNächste Zentralübung: Mi. 02.11.2005Nächste Vorlesung: Mo. 07.11.2005Nächste Miniklausur: Mi. 09.11.2005

Documents

1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Einführung in Berechenbarkeit, Formale Sprachen und Komplexitätstheorie Wintersemester