Kellerautomat (PDA) - Einfach erklärt | Simplexity
Simplexity
https://www.youtube.com/watch?v=bFWd7xOdpOM

Transkript (automatisch erstellt)

0:00 heute geht es um den kellerautomaten bzw PDA wir haben ja bereits den NEA bzw da kennengelernt mit dem es uns möglich war eine beliebige reguläre Sprache zu
0:10 erkennen und so ein automatenmodell wollen wir jetzt auch noch für die Typ 2 Sprachen bauen also das heißt ein kellerautomat soll so konstruiert werden
0:19 dass Typ zwei Sprachen erkannt werden wie z.B a hoch n B h n mit n größer g 1 mit einem da bzw n konnten wir so eine Sprache wie auch in BN noch nicht
0:29 erkennen dass uns ja nicht möglich war so sicherzustellen dass wir genau gleich viele as wie BS haben der kellerautomat soll aber nicht zumächtig sein und Typ
0:37 einprachen erkennen wie z.B auch n B n C n also nachdem wir auch n B n erkannt haben wird sichergestellt dass wir nicht wieder die gleiche anzah an CS erkennen
0:47 können und die Lösung dafür dass wir dann eine Sprache wie auch in B erkennen können ist der Keller nach dem Last in first out Prinzip ein PDA ist als
0:56 sechupel dargestellt wir haben einmal Z Sigma Gamma Delta Z0 und ein Hashtag Z sind hierbei wie immer die Zustände Sigma das Alphabet und das was jetzt neu
1:07 dazu kommt ist Gamma das kelleralphabet nämlich haben wir bei einem kellerautomaten einen Keller in dem wir Zeichen speichern können und alle
1:15 Zeichen die wir dann in diesem Keller schreiben sind Elemente vom kelleralphabet dann haben wir Delta die übergangsfunktion die ist diesmal so
1:22 definiert dass wir haben z K sig Kre Gamma das heißt wir haben einen Zustand ein Zeichen das wir einlesen und ein ein Symbol das auf dem Keller steht das
1:32 Zeichen das wir hier lesen ist immer das oberste das sich auf dem Keller befindet nach dem Last in first out Prinzip also wir können nur das oberste
1:40 Zeichen auf dem Keller lesen und wir gehen dann in die Potenzmenge von zkreuzgamma Stern also wir gehen in einen neuen Zustand und Schreiben
1:48 beliebige Zeichen in den Keller wichtig hierbei ist dass wir die Potenzmenge haben das heißt wir haben ein nichtdeterministisches Modell wir werden
1:56 noch das Gegenstück den deterministischen kellerutomaten kennenlernen was dann im nächsten Video kommt Z0 ist der Anfangszustand und das
2:03 Hashtag ist unser Keller bottom Symbol das Keller bottom Symbol ist das Zeichen dass sich am Anfang am Boden des Kellers befindet und ist dafür da dass wir
2:12 wissen wann wir den Boden des Kellers erreicht haben vielleicht ist euch aufgefallen dass wir beim tbel keine Endzustände definiert haben das liegt
2:20 daran dass ein kellerautomat durch leeren Keller akzeptiert das heißt wir haben eine Konfiguration von Z0 also unserem Startzustand mit einem Wort W
2:29 und im Keller bottom Symbol und am Ende müssen wir dann ein Übergang mit Zep EP haben das heißt wir löschen am Ende das Keller bottom Symbol durch EPS sodass
2:38 unser Keller am Ende leer ist kommen wir jetzt zu einem Beispiel W haben hier die Sprache L = A hoch n B h n mit N gröer= 1 unser Tupel ist so definiert wir haben
2:48 Z0 Z1 als Zustände ab als Alphabet # a als kelleralphabet Delta Z0 und hashag unser kellerutomat sieht dann wie folgt aus durch diese Übergänge hier speichern
3:00 wir uns erstmal a in den Keller ein als erstes lesen wir erstmal ein A und löschen das Hashtag durch ein großes a das heißt wir löschen das Hashtag hier
3:09 und schreiben ein a stattdessen hin und für alle weiteren as die wir einlesen schreiben wir a in Keller rein das machen wir solange bis wir dann ein B
3:17 lesen dann gehen wir den nächsten Zustand über und löschen dabei das oberste a und mit jedem weiteren B löschen wir dann immer wieder das
3:24 oberste a aus dem Keller raus und das machen wir sol lang bis dann der Keller leer ist und wenn der Keller leer ist wissen wir dass das Wort akzeptiert wird
3:33 hier sieht man dann auch dass der kellerautomat kein Zustand braucht sondern akzeptiert wenn der Keller leer ist und die Eingabe fertig eingelesen
3:41 wurde wir können uns jetzt noch die konfigurationsfolge von einem beispielwort wie z.B AAA BBB anschauen am Anfang starten wir in Z0 haben das
3:51 Wort und unser Keller bottom Symbol durch das erste eingelesene a schreiben wir ein großes a in den Keller dann lesen wir wieder ein a ein und schreiben
3:59 wieder ein großes a in den Killer und dann lesen wir noch ein A und schreiben noch ein a in den Killer dann lesen wir ein B gehen in den Zustand Z1 über und
4:08 löschen das erste a vom Keller dann lesen wir noch ein B Löschen wieder das oberste a und dann lesen wir wieder ein B und Löschen wieder das oberste a bis
4:17 wir dann am Ende diesen Übergang hier haben mit z1yy jetzt ist unsere Eingabe fertig eingelesen und der Keller ist leer was
4:25 heißt dass das Wort akzeptiert wird schauen wen un es noch ein Wort an was nicht in der Sprache liegt wie z.B AAA BB wir fangen wieder ein Z0 an und lesen
4:33 ein a wodurch wir wieder das Keller bottom Symbol durch ein a austauschen bis wir dann wieder bei derselben Konfiguration Z0 BB AAA landen gehen
4:43 dann durch das erste B in den Zustand Z1 über und löschen das erste a dann lesen wir wieder ein B und löschen das oberste a aus dem Keller so dass wir dann den
4:52 Übergang Z1 y a haben und das sagt uns jetzt dass das Wort nicht akzeptiert wird da die Eingabe fertig gelesen wurde aber der Keller immer noch nicht leer
5:01 ist schauen wir uns noch ein weiteres Beispiel für ein PDA an W h die folgende Sprache l = W1 Dollar W2 mit W1 W2 ist aus ab Stern und wir haben dreimal so
5:13 viele a im ersten Wort wie BS im zweiten Wort unser PDA ist wie folgt definiert im ersten Zustand q0 speichern wir jetzt für jedes a das wir einlesen 3 A im
5:24 Keller ein und durch B lass mir den Keller so wie er ist also wir schreiben nichts rein und löschen auch nichts dann wenn wir ein Dollar lesen gehen wir
5:32 von q0 in Q1 über wenn wir Ars lesen ändern wir nichts am Keller und durch jedes B das wir einlesen löschen wir ein a aus dem Keller und damit ist dann
5:41 unsere Bedingung erfüllt da wir immer dre BS für ein a einlesen müssen und dann haben wir noch einen EP #ep Übergang zu Q2 was dann unser nzustand
5:51 ist das eine weitere Eigenschaft des pdaas nämlich kann ein PDA auch durch nzustand akzeptieren also das heißt er kann durch nzustand und leeren Keller
6:00 akzeptieren das heißt mit diesem letzten Zusand müssen wir den Keller gar nicht lernen sondern er wde auch so akzeptieren hierbei spielt es keine
6:07 rollle ob man den PDA durch leeren Keller oder nzustand akzeptieren lässt da die seh äquivalent sind und dann habe ich noch ein letztes Beispiel für die
6:15 Sprache l = c hoch n a hoch m B hoch n + 1 mit nm größer= 1 der PDA funktioniert ähnlich wie der PDA für a hoch n B hoch n in unserem Startzustand q0 speichern
6:28 wir uns erstmal die an an CS im Keller ein wenn wir dann ein a lesen gehen wir in den Zustand Q1 über und können dann dort eine beliebige Anzahl an as lesen
6:38 wenn wir dann ein B lesen gehen wir dann weiter in den Zustand Q2 und löschen hier bei ein C aus dem Keller und in Q2 lesen wir dann sol lang B bis wir alle
6:46 CS aus dem Keller gelöscht haben und da wir die Bedingung haben dass wir ein B mehr als CS lesen sollen da wir ja hier C hoch n B hoch n + 1 haben gehen wir d
6:56 mit einem B # Übergang in Q3 löschen hierbei das Hashtag aus dem Keller und Lehen dadurch den Keller und akzeptieren dann das Wort hierbei ist es sinnvoll
7:05 noch mit einem Zustand wie Q3 zu arbeiten da wir am Ende noch ein B lesen müssen und womit wir dann den Keller leeren können da werden wir direkt am
7:13 Anfang das Keller bottom Symbol durch ein C #cb gelöscht hätten hätten wir nicht sicherstellen können dass wir noch ein B am Ende des Wortes lesen müssen um
7:21 das Wort zu akzeptieren kommen wir noch am Ende zu wichtigen Sätzen zum kellerautomaten lich wie bei den regulären Sprachen
7:28 existiert für für jede kontextfreie Sprache ein entsprechender PDA der diese Sprache akzeptiert außerdem kann jeder PDA in ein äquivalenten PDA mit nur
7:38 einem Zustand umgewandelt werden das heißt diesen PDA den wir hier gebaut haben den können wir auch in ein PDA umbauen der nur einen Zustand hat und
7:49 wie bereits gesagt kann ein PDA entweder mit leerem Keller oder mit nzustand akzeptieren und außerdem habe ich vergessen zu sagen dass ein
7:56 kellerautomat außerdem nicht mehr weiter arbeitet wenn der Keller ist das heißt wenn wir z.B be diesem PDA hier die Eingabe AAB BBB hätten durch die zwei a
8:06 würden wir uns dann zi a in den Keller schreiben und durch die ersten zwei BS würden wir diese dann wieder löschen das heißt der Keller wäre dann leer aber wir
8:13 haben noch ein B einzulesen also hätten wir diesen Übergang hier mit Z1 by W ich wir sehen dass das Wort nicht akzeptiert wird da wir zwar noch ein Zeichen
8:23 einzulesen haben aber der Keller bereits leer ist