Please enable JavaScript.
Coggle requires JavaScript to display documents.
A KE 3 Minimierung DEAs Grenzen REG (Myhill-Nerode ≡L # (Beisspiel (Sei…
A KE 3
Minimierung DEAs
Grenzen REG
kollabierter Automat
Q = {[q] | q element Q}
[q] = Äquivalenzklasse
#
Zustände des Automaten bestehen aus Äquivalenzklasen
Beisspiel
[q1] = {q1,q3}
[q2] = {q2, q4}
Myhill-Nerode ≡L
#
Myhill-Nerode = Minimaler Automat
zu Zeigen:
kollabierter Automat M'
hat genausoviele Zustände wie der MN-Automat zu L(M')
Alle nicht erreichbaren Zustände sind im kollabierten Automaten gestrichen.
Im kollabierten Automaten enden alle Läufe der Wörter einer Äquivalenzklasse, im selben Zustand
Satz
Beweis
Es muss also ein DEA existieren, wenn MN Relation Endlich ist.
MN-Relation enthält genausoviele Klassen wie der kollabierte Automat Zustände hat, also hat die MN-Relation endlichen Index
Hat die MN-Relation endlichen index ist der MN-Automat ein DEA
Sprache L ist regulär, wenn ihre MN-Relation endlichen Index hat
Index = Anzahl Äquivalenzklassen
Relation
:red_flag:
Zwei Wörter stehen w1, w2 stehen in Relation zueinander
wenn beide zu L, oder nicht zu L gehören
und bel. Suffix nichts daran ändert
Wörter über ≡L ML-Relation zu Äquivalenzklassen zusammenfassen
Beisspiel
Sei L={w∈{a,b}* | w endet auf aa}
Äquivalenzklassen
[ε] = {w | w endet nicht auf a}
[a] = {w | w endet auf a aber nicht auf aa}
[aa] = {w | w endet auf aa}
Ob eine Sprache Regular ist oder nicht!
Table Filling Algorithmus
Vorgehen
Suchphase
keine Markierung = fertig
sonst neuen Durchlauf starten
alle nichtmarkierten Pärchen prüfen
paar (p,q)
Prüfen ob für alle a element ∑
(∂(p,a),∂(q,a)) markiert?
-> markieren
unmarkierte Zustände = Äquivalente Zustandspaare
Initialisierung
markiere alle Paare die sich durch ɛ trennen lassen
(akzeptierend und verwerfend)
Beisspiel
Init
Suchphase
alle nicht markierten Pärchen prüfen
kollabierter Automat
Äquivalenzklassen
[0]={0}
[1]={1}
[2]={2,3}
[4]={4}
Pumping Lemma
#
Wenn eine Sprache regulär ist
ist sie auch pumpbar!
Idee
DEA mit k Zuständen, |Eingabewort| > k
1 Zustand muss mind. 2x besucht werden (schleife)
Pumpen = Schleife beliebig oft durchlaufen
Jeder Lauf aufteilbar in
Startzustand (q0) bis zum 1. Auftreten von qj
Auftreten von qj bis zum 2. Auftreten von qj
Auftreten von qj bis Ende (qk)
Definition
Eigenschaften
|y| > 0
∀i ≥ 0 : xyiz ∈ L
|xy| ≤ k
Sprache ist Pumpbar wenn ein Wort
w = xyz
Zerlegung hat für die folgende Eigenschaften gelten
Spiel
Sie wählen w aus L, Mindestlänge k
GS wählt zerteilung w=xyz mit |xy| ≤ k und y≠ɛ
GS wählt Zahl k aus N
4.Finde ein i aus N für das x yi z ∉ L
-> gefunden? Dann sprache nicht pumpbar
Anwendung
Annahme: L ist REG
müsste DEA mit k zuständen geben, der L akzeptiert
Zeigen, dass so ein DEA nicht existiert
Begriffe
Äquivalente Zustandspaare p ≈ q
egal in welchem der Zustände man Sich befindet, nächster Übergang landed für beide entweder in Akzeptierenden oder Verwerfenden zustand
trennbare Zustände
Trennwort
Wort für welches sich der Folgezustand unterscheided
z.B. ɛ wenn einer akzeptierend, der andere Verwerfend ist
q1, q2 trennbar
Trennwort 1
Rechtskongruenz
Aus u ≡L v folgt für beliebige x ∈ Σ*: ux ≡L vx
Nachweiß von Nichtregularität
:pen: zum finden Äquivalenter Zustände f.
kollabierten Automaten
