Upload
anneken-gerten
View
105
Download
0
Embed Size (px)
Citation preview
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