Zentralübung 10. Dezember 2008 Algorithmen und Datenstrukturen (EI)

Zentralübung

10. Dezember 2008

Algorithmen und Datenstrukturen (EI)

Stefan Schmid @ TU München, 2008 2

Frage:

Gegeben eine reguläre Sprache L1.

Gegeben eine andere Sprache L2 welche eine Teilmenge aller

Strings von L1 enthält, das heisst:

L2 ½ L1

Ist dann L2 auch regulär?

Appetizer...

Stefan Schmid @ TU München, 2008 3

Nein! Gegenbeispiel: L1 ist die Sprache {0,1}*, und

L2 ist die Sprache {0k 1k | k ¸ 0}...

Appetizer...

Stefan Schmid @ TU München, 2008 4

Sprache {0k 1k | k ¸ 0} ist nicht regulär. Appetizer...

Veranschaulichung über endlicher Automat:

bei n Uebergängen muss man mindestens

einmal einen Zustand mehr als einmal besucht

haben. Diesen Teil kann man beliebig oft wieder

holen (oder auch weglassen!), und das neue

Wort muss auch in der Sprache sein.

Stefan Schmid @ TU München, 2008 5

Sprache {0k 1k | k ¸ 0} ist nicht regulär.

Appetizer...

1. „Kreativer Teil“: betrachte das Wort 0n1n 2 L (für ein n das gemäss Pumping Lemma existiert)

2. Es muss eine Unterteilung uvw geben für 0n1n

3. Wegen Bedingung 2 besteht uv ausschliesslich aus a‘s, und v ist nicht leer (Bedingung 3)

4. Gemäss Lemma muss uv2w = an-|v|a2¢ |v|bn auch in L sein => Widerspruch, da dieses Wort mehr a‘s als b‘s hat.

5. Also Sprache nicht regulär!

Stefan Schmid @ TU München, 2008 6

Achtung: Pumping Kriterien können auch für

nicht-reguläre Sprachen gelten. D.h. Pumping

Lemma kann gebraucht werden um zu zeigen,

dass eine Sprache nicht regulär ist, aber nicht um

zu zeigen dass eine Sprache regulär ist (= regulärer

Ausdruck angeben o.ä.)!

Appetizer...

Stefan Schmid @ TU München, 2008 7

Sprache {0k 1k | k ¸ 0} ist nicht regulär.

Appetizer...

Ist sie kontext frei?

Ja, Beweis durch Grammatik:

S => T | T => 0T1 | 01

Stefan Schmid @ TU München, 2008 8

Appetizer...

Beispiel aus Vorlesung reloaded...

r = Zykluslänge

Idee: hänge einen Zyklus mehr an...

Stefan Schmid @ TU München, 2008 9

Appetizer...

Gilt das Umgekehrte? Sei wieder L2 ½ L1, aber nun sei

L2 regulär. Ist dann L1 auch regulär?

Stefan Schmid @ TU München, 2008 10

Nein! Gegenbeispiel: L2 ist die Sprache über dem

deutschen Alphabet {a,b,c,...,x,y,z} bestehend

aus dem String sugus, und L1 ist die Sprache

aller Palindrome über diesem Alphabet.

Appetizer...

Stefan Schmid @ TU München, 2008 11

Bemerkung zu Kombination von Automaten

Machine für L1 Å L2?

Entweder auch über de Morgan!

Oder über Kreuzproduktmaschine!

Stefan Schmid @ TU München, 2008 12

Bemerkung zu Kombination von Automaten

Oder über Kreuzproduktmaschine!

Mache Kreuzprodukt der Zustände.

Idee: lasse beide Maschinen laufen;

beide Transitionen!

Akzeptiere nur wenn beide

Maschinen akzeptieren.

Stefan Schmid @ TU München, 2008 13

Appetizer...

Erinnerung: NEA (inkl. -Übergänge)

und DEA sind äquivalent!

Verfahren um aus NEA einen äquivalenten DEA zu bauen:

Potenzmengenkonstruktion

Stefan Schmid @ TU München, 2008 14

Appetizer...

Verfahren:1. Beginne im Startzustand, bestimme Menge aller Zustände die man

in einem Schritt erreicht für ein gegebenes Inputzeichen => neuer

Zustand.

2. Von einem Mengenzustand gehe zu neuem Zustand definiert durch

alle möglichen (über alle Zustände in Menge) Uebergänge eines Inputzeichens.

3. Akzeptierender Zustand: alle Mengenzustände die mind. einen akzeptierenden Zustand enthalten

4. Startzustand: urspr. Zustand plus Epsilonhülle

Stefan Schmid @ TU München, 2008 15

Appetizer...

Es ist nicht nötig, alle Zustände der Potenzmenge anzugeben!

Es genügen die erreichbaren!

Stefan Schmid @ TU München, 2008 16

Stefan Schmid @ TU München, 2008 17

Stefan Schmid @ TU München, 2008 18

Kann noch vereinfacht werden,

z.B. Zustand {0} und {0,1} kann

nicht erreicht werden.

Stefan Schmid @ TU München, 2008 19

Welche Strings sind in (L)??

1 (weil 10 2 L)

11 (weil 1101 2 L)

10 (weil 1000 2 L)01 (weil 0101 2 L)

00 (weil 0010 2 L)

Stefan Schmid @ TU München, 2008 20

Welche Strings sind in (L): Allgemeiner??

Beobachtung: es gibt von jedem Zustand aus einen Weg, der in

zwei Schritten zu einem akzeptierenden Zustand führt!

z.B. von q0 durch „10“, von q1 durch „00“, von q2 durch „01“

Stefan Schmid @ TU München, 2008 21

Beobachtung: es gibt von jedem Zustand aus einen Weg, der in

zwei Schritten zu einem akzeptierenden Zustand führt!

z.B. von q0 durch „10“, von q1 durch „00“, von q2 durch „01“

Folge: alle Strings der Länge ¸ 2 sind in (L)!

Plus String „1“ wie bereits gesehen. Also nur „0“ nicht! (Im obigen Automat

kommt man mit 0x nicht zu einem akzeptierenden.)

Stefan Schmid @ TU München, 2008 22

Folge: alle Strings der Länge ¸ 2 sind in (L)!

Plus String „1“ wie bereits gesehen. Also nur „0“ nicht! (Im obigen Automat

kommt man mit 0x nicht zu einem akzeptierenden.)

Stefan Schmid @ TU München, 2008 23

Beispiele für L?

10101010 2 L? Ja!

0000111 2 L? Ja!

0011011001 2 L? Nein!

Stefan Schmid @ TU München, 2008 24

Allgemein:

zuerst beliebiger String ohne benachbarte Einsen,

dann beliebiger String ohne benachbarte Nullen.

Beliebiger String ohne benachbarte Einsen?

(10|0)*(|1)

Beliebiger String ohne benachbarte Nullen?

(01|1)*(|0)

Kombination / Resultat?

(10|0)*(|1)(01|1)*(|0) = (10|0)* (01|1)*(|0)

Stefan Schmid @ TU München, 2008 25

Methode: per Induktion über die erlaubten Zustände!

Stefan Schmid @ TU München, 2008 26

Achtung: aufwendig! Für n Zustände:

n Induktionsschritte, mal n mal n Wege! (in unserem Fall 3^3 = 27)

Induktionsanfang / erster Schritt:

Stefan Schmid @ TU München, 2008 27

Bessere Methode (zumindest zum Prüfen?):

Verallgemeinerte endliche Automaten!

1. Füge Hilfszustände ein für Start und Ende

2. Entferne einen Zustand nach dem anderen, und ersetze

Inputzeichen an den Kanten durch entsprechende reguläre

Ausdrücke!

3. Am Schluss lässt sich der reguläre Ausdruck an verbleibender

Kante ablesen!

Stefan Schmid @ TU München, 2008 28

s

a

Entferne Zustand q2!

Uebergänge zw. verbleibenden Zuständen:

q0 q1

Füge neuen Anfangszustand

und Endzustand ein!

Stefan Schmid @ TU München, 2008 29

Entferne Zustand q2!

Uebergänge zw. verbleibenden Zuständen:

q0 q1

Entferne Zustand q0!

Uebergänge zw. verbleibenden Zuständen:

q0 q1

Stefan Schmid @ TU München, 2008 30

Was bei mehreren akzeptierenden Zuständen?

Analog. Alle Pfade lassen...

Methode:

Stefan Schmid @ TU München, 2008 31

Methode:

Stefan Schmid @ TU München, 2008 32

Methode:

Stefan Schmid @ TU München, 2008 33

Stefan Schmid @ TU München, 2008 34

Stefan Schmid @ TU München, 2008 35

Zusatzaufgabe:

Stefan Schmid @ TU München, 2008 36

Zusatzaufgabe:

Stefan Schmid @ TU München, 2008 37

Zusatzaufgabe:

Stefan Schmid @ TU München, 2008 38

Zusatzaufgabe:

Stefan Schmid @ TU München, 2008 39

Notes

Stefan Schmid @ TU München, 2008 40

Notes

Stefan Schmid @ TU München, 2008 41

Notes

Stefan Schmid @ TU München, 2008 42

Notes