(3) Endliche Automaten
Tübingen Machine Learning
https://www.youtube.com/watch?v=zjLS3YgKOkI

Transkript (automatisch erstellt)

0:00 in der letzten vorlesung haben wir uns angeguckt was wörter alphabete und sprachen sind und das war die voraussetzung die wir gebraucht haben
0:08 damit wir heute uns angucken können was sind endliche automaten und in diesem fall endliche deterministische automaten wir werden später auch die nicht
0:18 deterministischen zehnter fangen aber mit der einfachen variante den deterministischen automaten noch mal was ist was wollen wir mit einem endlichen
0:26 automaten erreichen ein endlicher automat sollen berechnungsmodell sein soll das einfachste computermodell sein was man
0:33 sich nur vorstellen kann und ich habe das in der letzten vorlesung schon kurz erklärt ich mache es aber einfach noch mal weil es hier auch gut hin passt was
0:40 soll so ein computermodell können na ja der computer der soll halt eingaben verarbeiten können das ist irgendwie offensichtliche wollen
0:47 das eintippen können und das werden wir tun mit leitern und aus einer bestimmten sprache oder beziehungsweise mit wörtern über einen bestimmten alphabet dann
0:55 sollte er was berechnen können der soll was speichern können und vielleicht auch eine ausgabe produzieren kann so und selbst nehme ich an werden
1:04 sie wahrscheinlich ein bisschen enttäuscht sein sohn endlich automat automat ist wirklich was total einfaches und ich zeige ihnen das am beispiel von
1:11 einer kaffeemaschine die in der mensch ist mensch steht also stellen sie sich folgendes vor eine ganz einfache kaffeemaschine gar nicht so kompliziert
1:17 wie das ding was wir haben sondern eine einfache kaffeemaschine die kann verschiedene dinge die kann zehn cent und 20 cent münzen annehmen das ist
1:26 sozusagen die eingabe also das alphabet wenn sie wollen besteht aus zehn cent unter 20 cent münzen die kann man da reinschmeißen und wenn man 30 cent
1:36 eingeschmissen hat dann macht die maschine einfach einen kaffee fertig eine sorte café nichts auswahl wählen cappuccino oder milchkaffee oder weiß
1:43 der geier was die maschine hat den staat zustand in dem wartet sie und wenn dann 30 zentren sind dann gibt sie uns einen kaffee im becher muss so und wie könnte
1:54 man das jetzt will man versucht das jetzt systematisch zu beschreiben mit verschiedenen zuständen in denen die maschine sein sollte wie würde das sein
2:00 ich habe hier unten so ein bild gemalt also die wir fangen an einem start zustand da wartet die maschine bis jemand kommt
2:06 und jetzt können verschiedene dinge passieren man kann also zehn oder 20 cent stücke ein schmeißen jetzt kann sein dass jemand einen cent
2:13 stück einspeist dann muss die maschine die geht jetzt in den richten wir nennen diese dinge zustände also diese knubbel hier also diese
2:20 kreise auf den bildern sind zustände dass eines der stadt zu stadt und das nächste ist jetzt der zustand in dem die maschine ist nach dem 10 cent bezahlt
2:27 worden sind die maschine muss ich das ja irgendwie merken weil es fehlt ja noch was also sie kann jetzt noch nicht ein kaffeehaus
2:33 tun und irgendwie muss sie sich merken dass zehn cent bezahlt worden und der endlich das wird später sieht ein automat genauso aus das passiert dadurch
2:40 dass die maschine einen bestimmten zustand hat der bedeutet zehn cent bezahlt also jetzt sind wir zb in diesem zustand zehn cent bezahlt und dann
2:49 schmeißt man noch mal zehn cent rein dann ist man im zustand 20 cent bezahlt jetzt kann man nochmals hinschmeißen und dann macht die maschine kaffee und das
2:58 ist der endzustand endzustand in so einem ausgabe zustand oder naja ich erkläre es später das ist ein besonderer zustand der hat zwei kringel drumrum
3:07 akzeptieren dazu stand da würde man sagen die kaffeemaschine hat jetzt akzeptiert dass ich genau 30 cent eingeschmissen habe macht mir einen
3:13 kaffee jetzt sieht man hier das zum die maschine an verschiedenen stellen ja verschiedene eingaben kriegen kann also im zustand könnte ich zehn cent
3:22 reinschmeißen dann komme ich in den zustand von zehn cent bezahlt ich könnte aber auch gleich 20 cent reinschmeißen dann komme ich in den zustand 20 cent
3:30 die zahl und genauso in dem zustand hier in dem ersten wo ich schon zehn cent bezahlt könnte ich 10 10 reinschmeißen und 20 cent und kommen jeweils in
3:39 verschiedene weitere zustände jetzt ist es manchmal so in dem dritten zustand zum beispiel sind schon 20 cent bezahlt ich könnte jetzt also wenn ich
3:47 zehn vereinsmeisters klar mach das ding im café ich könnte aber auch 20 cent reinschmeißen das erlaubt die maschine hier aber gar nicht sie wird vielleicht
3:54 einfach wieder ausspucken oder so also hier ist von diesem 20 cent zustand ist gar kein veilchen der sagt was passiert und mit 20 cent man könnte
4:03 das jetzt wenn man will explizit modellieren manchmal ist es auch so dass man sagt in den bestimmten zustand ist eine
4:09 bestimmte eingabe nicht erlaubt und deswegen steht egal ob es ein bildchen mit 1 aber das ist der prototyp von dem endlichen automaten und jetzt versuchen
4:18 einmal diesen automaten uns mit den bezeichnungen zu versehen die wir gleich brauchen um formale nun endlich ein automat aus der informatik
4:25 aufzuschreiben also ich habe schon gesagt die der automat startet immer in einem zustand es ist der staat zustand und der heißt
4:33 auch so stand zu stand der ist immer eindeutig definiert bei einem automaten gibt es einfach alles normal vereinen stadt zu stadt
4:39 dann kann der automatisch verschiedene eingaben lesen das sind die die hier immer auf den veilchen stehen im üblichen in der
4:47 informatik wir werden das gleich sehen sind es typischerweise buchstaben aus einem bestimmten alphabet dann jeder von diesen kringeln heißt zustand als
4:54 unendlicher automat kann endlich viele zustände annehmen daher kommt auch das wort endlich also das bezieht sich auf die anzahl der zustände dieser automat
5:02 hat und wenn sie so wollen sind die zustände sind so etwas wie das gedächtnis von dem automaten der kann sich nicht viel merken
5:10 das einzige was da über seine vergangenheit weiß ist in welchem zustand er gerade ist oder was er über die eingabe also liest eine eingabe die
5:17 besteht jetzt aus mehreren buchstaben zum beispiel also hier einmal zehn cent und nochmals sind sender dann bin ich halt in dem zustand der automat und der
5:25 automat benutzt diesen stoß zustand zum beispiel um sich zu merken dass halt schon 210 10 cent stücke drin sind dann diese ganzen veilchen eben wo ich von
5:35 welchem zustand ich mit welchem mit welcher eingabe in welchen nächsten zustand kommen dieses ding heißt die übergangs funktion
5:42 des automaten das heißt die übergangs funktion beschreibt durch wie ich von einem zustand sind oder wenn ich einen neuen buchstaben
5:49 lesen ich eine neue eingabe krieg und ich bin den zustand aber in welchem zustand komme ich dann und bei dem deterministischen automaten ist es auch
5:57 so dass das immer eindeutig definiert sein wird in welchem zustand nicht angenommen und dann gibt es en zustände die haben hier so ein krieger komme ich
6:06 gleich noch drauf die heißen bei den automaten akzeptieren die zustände dies sind mit solchen kringeln bezeichnet da sagt dann der automat die eingabe war
6:15 war richtig oder in einer bestimmten form ich erkläre es gleich aber wenn wir jetzt auf der nächsten folie uns dann die formale definition anschauen dann
6:23 haben sie einfach dieses bild ein bisschen im kopf weil die formale definition die ist jetzt wieder so ein typisches mathematisches konstrukt was
6:33 ich erst mal ziemlich abstrakt anhört und auch nicht so besonders einladend wirkt ehrlich gesagt es hängt also wie folgt an ein endlicher deterministische
6:43 automat wird beschrieben durch ein fünftel jetzt wiesmann schon 15 denkt sich auch das ist aber umständlich aber es hilft an der stelle nicht so
6:50 umständlich ist es hat also und der automat besteht aus einem fünftel aus ein fünftel sind erstmal fünf sachen die immer genau in dieser reihenfolge in der
6:59 definition stehen und jetzt ist die frage was sind diese fünf sachen also die erste sache ist q das ist die endliche menge von zuständen
7:07 also wir haben in diesem automat gesehen der hat diese verschiedenen runden 30 gehabt die zustände bei nach definition von endlichen automat besteht einfach
7:17 die zustands menge aus endlich vielen sachen die müssen keinen bestimmten namen haben wir können die zustände zustand 1 zustand 2 und so weiter
7:24 benennen das ist eigentlich egal für alles weitere wichtige ist wir haben endlich viele solche zustände dann gibt es ein alphabet sigma naja
7:35 also ähnliche menge das alphabet also wir müssen wissen was sind die zustände von dem automaten müssen wissen was ist das alphabet also welche buchstaben kann
7:43 diese alpha dieser automat überhaupt lesen dann geld hat die übergangs funktion also delta ist jetzt eine funktion die geht von q kreuz sigma nach
7:53 kuh das heißt es jetzt wo ist die menge der cd eingabe in die funktion ist ein zustand und ein buchstabe und die ausgabe der funktion
8:03 ist ein neuer zustand und das bedeutet ich bin also die der zustand hier vorne ist er in dem ich gerade bin ich lese einen weiteren buchstaben und der
8:12 zustand den die funktion aus gibt es dann der neue zustand in dem ich gerade das war das was wir in den bildchen vorne immer mit den pfeilen gezeichnet
8:19 hatten dass diese pfeile stellen die übergangs funktion dar schon jetzt gibt es noch zwei spezielle zustände oder es können auch mehrere
8:27 seien aber jetzt fangen wir machen hier also der staat zustand kuh 0 der ist immer das ist im normalfall einer der ist einfach einer dieser
8:34 zustands menge wird einfach definiert indem fängt das ding an also der kaffeeautomat zum beispiel ist im staat zustand dass kein geld ein geschmissen
8:41 worden ist und dann gibt es eine menge f von akzeptierenden zuständen das können auch mehrere sein die heißen also ich habe da meine weiß
8:50 ich nicht 17 zustände und vielleicht sind drei davon akzeptieren die zustände weil vielleicht kann ich in dem kaffeeautomaten die 30 cent eingeben und
8:57 vielleicht habe ich auch eine was ich habe ich einen gutschein und wenn ich den eingekriegt auch ein café und das ist dann vielleicht andere endzustand
9:03 aber ich krieg am schluss auf dem kaffee damit raus zum beispiel so und der endlich automat formal gesehen besteht jetzt eben einfach hier oben ich gehe
9:11 noch mal da hoch auf die reihe dieser definitionen also wir brauchen eine endliche menge von zuständen wir brauchen ein alphabet wir brauchen
9:19 übergangs funktion wir müssen wissen in welchem zustand fangen wir an und wir müssen wissen was sind akzeptierende zustände und wir
9:28 machen hier einfach mal ein paar beispiele dass man so ein bisschen im gefühl jenseits von kaffeeautomaten dafür kriegt also die automaten die wir
9:35 jetzt sehen also es hilft sehr oft oder das ist eigentlich das einzige was irgendwie hilft ist sich diese automaten immer zu versuchen aufzumalen und sie
9:41 sehen das jetzt hier auch da ist jetzt ein bildchen von so einem automaten diese bildchen heißen irgendwie zustands diagramme oder es gibt auch andere aber
9:49 ich habe eigentlich keinen so richtig festnahmen das ist einfach das bildchen was diesen automaten symbolisiert und die funktionieren im normalfall so es
9:57 gibt keinen staat zustand und der wird dadurch angezeigt dass es einen pfeil aus dem nichts in diesem zustand hinein gibt also das ist immer der staat
10:04 zustand auf denen dieser pfeil aus dem nichts hinzu und die akzeptierenden zustände die haben immer zwei kreise außenrum bei der
10:11 anderen zustände haben wir uns nochmal einen kreis und die übergangs funktion besteht halt aus pfeilen wo über dem pfeil immer steht mit welchen buchstaben
10:18 mich von diesem zustand in den nächsten kommen würde und hier sehen wir jetzt also zum beispiel einen automaten dass das
10:25 bildchen können sie selber sehen als unbefangen im zustand q1 an wenn wir nun lesen sagt dass wir bleiben im zustand q1 wenn wir eine 1 lesen
10:35 heißt dieses bildchen dann kommen wir in zustand gut sein und wir können jetzt also auch wenn dessen akzeptieren da zustand ist das heißt nicht dass wir
10:42 nicht weiter lesen können also wenn unsere eingabe ist als viele buchstaben hat kann sein dass es weitergeht und jetzt könnte sein dass wir eine 1
10:48 lesen dann bleiben wir in diesem zustand q1 dann lesen dass vielleicht 0 kommen diesen zustand q3 und dann zb aus wenn wir 0 oder 1 lesen das ist das was hier
10:59 im moment genannt wird dann kommen wir von q3 wieder nach q2 und wir sehen jetzt also wenn man jetzt die ganz formelle definition von diesem automaten
11:09 hinschreiben will dann reicht das bildchen nicht wenn man es ganz normal machen wir muss man halt sagen der automat besteht aus diesen fünf toten
11:15 das sind fünf sachen drin also was ist da drin der die zuschauermenge besteht aus drei zuständen q1 bis q3 das alphabet besteht aus 0 1 die übergangs
11:26 funktion die habe ich jetzt hier in der tabelle hingeschrieben delta wo ich praktisch einfach hin geschrieben habt immer den also die übergangs funktion im
11:33 jahr zwei argumente den zustand und den buchstaben und dann steht eben drin wo man landet also hier zb wenn ich im zustand q1 bin und ich lese eine null
11:42 dann lande ich wieder im zustand q1 genau und auf diese weise ich hoffe ich habe keinen fehler gemacht habe ich jetzt die übergangs funktion die oben in
11:50 dem bildchen illustriert das habe ich jetzt versucht hier hin zu schreiben so praktisch bei jedem zustand steht durch welche also und zwar und auch für jede
11:58 eingabe die möglich ist an der stelle wo komme ich als nächstes hin so was brauchen wir noch das sind die zustände das ist die übergangs funktion dann
12:06 brauchen wir den staat zustand des q1 und die menge der and zustände in diesem fall besteht aus einem zustand nämlich 2 genau das ist jetzt die formale
12:16 definition von einem außer ein beispiel für einen automaten jetzt ist eine sache die ich an der stelle ansprechen will also das
12:26 ärgerliche ist hinter theoretischen informatik gibt es zwar viele bücher aber es gibt nicht so eine übergreifende konvention und viele autor machen viele
12:33 sachen immer ein bisschen anders eine sache die wichtig ist ob die übergangs funktion eine partielle oder eine totale funktion ist partielle
12:43 funktion heißt es gibt zustände wo vielleicht ein buchstabe drüber steht aber dann nicht steht weil also es wohl nicht definiert ist was dann passieren
12:50 soll also in dem kaffeeautomaten hat wird das gesehen wenn schon 20 gehen nochmal zurück hier sind schon 20 cent eingeschmissen und ich könnte an der
12:59 stelle jetzt auch wieder 20 cent ein schmeißen aber hier steht inzwischen bildchen gar nicht drin was dann passiert das heißt die übergangs
13:05 funktion ist an der stelle nicht komplett nicht total definiert also total definiert heißt für jede kombination von zuständen und buchstaben
13:12 die prinzipiell gelesen werden können uns eigentlich was rauskommt und hier habe ich jetzt eben nicht gesagt was passiert wenn 20 cent eingeschmissen
13:18 werden da soll irgendwie das soll nicht vorkommen oder das interessiert mich nicht an der stelle was man so und jetzt und andere autoren sagen die übergangs
13:28 funktions halt immer komplett definiert seien total ich muss für jeden zustand alles ist es ist dieses fenster hier wie komme ich da jetzt wieder runter so
13:39 [Musik] genau und das ist der unterschied zwischen totaler und partieller übergangs funktion
13:45 ich gebe normalfall davon aus dass die übergangs funktion total ist das heißt alle übergänge sind definiert und der witz ist man kann von dem einen sehr
13:53 einfach zum anderen über gehen und ich habe das hier unten gezeichnet also hier haben wir zum beispiel den beiden den automaten dessen alphabet zu null und
14:00 eins sein aber ich habe also man sieht zum beispiel den zustand q1 ist nicht definiert was soll passieren wenn er eins gelesen wird er steht nur wenn du 0
14:08 gelesen wird gemacht q2 aber was wenn er eins gelesen wird steht nicht so ein paar kannte ist jetzt in den anderen auto wenn man will dass die
14:16 übergangs fraktion wirklich total definiert ist kann man aus so einem automaten einen anderen automaten generieren indem wir ganz einfach einen
14:23 weiteren zustand hinzufügen führen jetzt einen zustand ein da heißt andy feind oder also irgendwie ein neuer zustand den es noch nicht gibt ja irgendwie ein
14:33 schritt der braucht auch keinen speziellen namen haben wir müssen uns nur merken dass das der zustand ist er immer dann heißt das ist umdefiniert
14:39 dann mache ich hier einen zustand hin wo ich zum beispiel von von dem automaten wenn ich eben eine 1 le soir q1 komme ich halt in diesem zustand und definiert
14:48 oder genauso in q2 auf der linken seite noch mal da ist nicht nicht klar was passieren soll wenn ich eine null ist dann mache ich in diesem automaten
14:55 rechts in den roten ein zeichen mit 0 von q2 nach an die wand und dann wahrscheinlich was hier an dieser stelle fehlt wenn ich das jetzt eigentlich eine
15:03 totale übergangs funktion machen will ist dass ich sage was passiert denn im zustand an die feind wenn ich null und eins lesen hat dann bleibe ich in diesem
15:09 zustand drin ich mal diesmal noch ein das ist jetzt bist du blöd weil nicht so viel platz ist also ich mache es von dem zustand an die scheint zu sich selbst
15:18 noch kommt man durch lesen von null und eins bleibt man einfach in diesem zustand also wenn man in dem einmal gelandet ist dann ist es aus dann bleibt
15:26 man einfach für immer in diesem zustand und es passt für eine intuition auch weil das was wir später machen wollen es wir interessieren uns immer dafür wird
15:34 ein wort vom automaten akzeptiert oder nicht lande ich wenn ich das wort gelesen habe im endzustand oder bin ich in irgendeinem anderen zustand jetzt auf
15:42 der anderen zustand irgendwie q1 ist oder an die feind ist mir dann egal also das wichtige ist natürlich dass dieser undefinierten zustand kein akzeptieren
15:49 der zustand sein was genau aber durch diese konstruktion kann ich immer von dem einen zum anderen übergehen und deswegen ist es eigentlich gar nicht so
15:57 wichtig ob wir am schluss sagen die übergangs funktion ist partiell oder total deswegen möchte ich das auch im weiteren
16:03 eigentlich gar nicht mehr groß diskutieren so was ist jetzt die berechnung eines automaten also wir haben jetzt erstmal
16:11 die formale definition hingeschrieben von so einem automaten und was ist jetzt eine berechnung eine berechnung von einem automaten besteht jetzt darin dass
16:18 der ein wort liest und zwar buchstabe für buchstabe und dabei die verschiedenen zustände durchläuft und eine berechnung des automaten können sie
16:27 uns jetzt mal anschauen was was das jedes formal definiert ist also eine folge es null bis sn von zuständen also eine berechnung ist ein zustand soll
16:37 also eine folge von zuständen heiß berechnung des automaten und der ist jetzt ist halt immer der automat m für maschinen also mit diesen fünf zutaten
16:47 hier also wir haben die folge von zuständen der automat berechnet und zwar aus dem wort w was aus dem buch stammen besteht
16:56 w1 bis wir in und wir sagen jetzt also seine zustand folge ist die berechnung des automaten bei eingabe dieses wortes w falls intuitiv gesprochen falls halt
17:08 der automat durch diese zustände durch geht wenn er jetzt die buchstaben des wortes wie abarbeitet das ist das was wir meinen wenn was formal hinschreiben
17:15 kommt folgendes raus also der staat zustand sollte 0 sein also die berechnung muss im staat zustand staaten s0 muss gleich zu null sein und jetzt
17:25 musste es passieren wenn wir einem zustand es eh schon sind und wir lesen jetzt den nächsten buchstaben des wortes das ist dann der buchstabe e plus 1 dann
17:37 muss die übergangs funktion delta uns in den zustand des e plus eins bringen das heißt wenn wir diese folge lesen dieses wir haben hier oben ließe es null
17:46 bis m und wir lesen er gleichzeitig das wort w1 bis wm und es muss halt immer so sein dass wenn ich halt den nächsten den nächsten buchstaben legst die
17:54 überwachungsfunktion mich dann auch in dieser folge es mich zur nächsten zustand bringt und das muss gelten für alle ii von null
18:02 bis m bis in -1 wahrscheinlich weil dann gibt's hier musste stehen das ist das
18:11 übliche bei schleifen weiß man nie ob sie bis ende oder +1 gehen oder ob sie bei null oder eins anfangen also diese fängt bei null an und muss bei -1 enden
18:20 das schreibe ich noch kurz hin - fans weil wenn ich im in - 10 zustand bin dann komme ich in den letzten zustand
18:32 und dann von dort aus geht es ja gar nicht mehr weiß als das ist eine berechnung des automaten und ich habe hier mal ein beispiel gemacht also das
18:40 ist der gleiche automat den wir vorher schon gesehen haben glaube ich auf dieser folie und jetzt können wir ein wort lesen also jetzt gucken wir dieses
18:47 wort an 001 und was ist jetzt die zustands folge also der staat zustand ist immer co q1 tschuldigung sie starten in q1 jetzt das passiert bevor wir den
18:58 ersten buchstaben lesen jetzt lesen wir den ersten buchstaben das ist null die null wenn wir das uns in dem automat angucken sorgt dafür dass
19:06 wir weiterhin in q1 bleiben deswegen schreiben wir hier q1 noch mal hin unsere zustand folge jetzt lesen wir nochmal eine null bleiben wieder in q1
19:14 das ist dieses dritte q1 hier und dann lesen wir jetzt 1 1 sie bringt uns hier in diesem zustand co2 das ist das was jetzt steht also das heißt sind die
19:24 berechnung des automaten bei eingabe des wortes 001 ist q1 q1 q1 q2 und das ergebnis der berechnung des kommt glaube ich auf der nächsten folge
19:35 also das ergebnis dieser wäre also die gesamte berechnung ist jetzt praktisch die folge der zustände aber am schluss interessiert uns eigentlich immer nur
19:42 was ist denn der endzustand und ist eher akzeptieren oder nicht in diesem beispiel ist jetzt kurz weiter akzeptierende zustand da freuen wir uns
19:49 oder ob man sich freut oder nicht ist ja egal so auf jeden fall ist es ein akzeptieren da zustand und das ist alles was uns da üblicherweise interessiert
19:58 und es kommt jetzt in der nächsten definition also eine berechnung akzeptiert ein wort falls die berechnung in einem akzeptierenden zustand endet
20:07 also ich mache die ganze berechnung wenn ich am schluss in so einem zustand mit zwei kriegen drohen bin sage ich der automat akzeptiertes wort oder diese
20:15 rechnung akzeptiertes wort und sonst eben nicht so und jetzt interessiert uns jetzt haben wir so einen automaten hier zum beispiel geben wir denen diesem bild
20:28 jetzt interessiert und was sind denn jetzt eigentlich die ganzen wörter die von diesem automaten akzeptiert werden würden also es gibt offensichtlich
20:34 weiter die akzeptiert werden und offensichtlich welche die nicht akzeptiert werden und können nur die irgendwie beschreiben und erst mal geben
20:43 wir jetzt den akzeptierten wörtern den namen wir sagen jetzt die von dem endlichen automaten akzeptierte sprache und die heißt also wenn der automat m
20:51 heißt weil es ist 11 die sprache als elfe language wieder im film maschinen also die sprache die von dieser maschine von diesem automaten akzeptiert wird und
21:00 was ist die straße das ist einfach die menge der wörter die von nm akzeptiert werden also und wenn man das formal hin schreibt also lm ist
21:08 dann definiert als diejenigen wörter über dem alphabet also sigma ist ja das alphabet ist natürlich hier gemeint auch das alphabet das alte automaten
21:19 es sieht man stern sind jetzt alle möglichen wörter und die erkannte sprache ist eben jetzt diese wörter für die gilt dass m akzeptiert wer also die
21:29 der automat endet in dem akzeptierenden zustand genau das ist eigentlich glaube ich auch ganz intuitiv klar eine sache die ich hier unten noch hin geschrieben
21:38 habe ist ganz wichtig so ein automat wenn der in einem akzeptierten zustand das kann die berechnung ruhig noch weiter gehen also hier das war jetzt ein
21:46 beispiel wo es nicht so habe ich kann man noch ein zu unterschreiben wo es vielleicht anders ist also wir machen noch ein
21:52 zweites beispiel wir lesen mal hier das wort 0 1 0 und was passiert dann wir starten in q1 war dass der staat zustand ist dann
22:04 lesen wir null und wir landen immer noch in q1 dann lesen wir eins und landen im q2 das ist eigentlich ein akzeptieren der zustand aber unsere eingabe ist halt
22:16 noch nicht zu ende die eingabe geht weiter jetzt kommt nämlich die eingabe 0 und damit landen wir jetzt im q3 und damit über rechnung auf das heißt wir
22:26 sind jetzt bei diesem wort durch den akzeptierten zustand durchgegangen aber der endzustand ist q3 der also hier wird nicht akzeptiert das wort obwohl
22:34 zwischendrin akzeptieren der zustand ist also und es ist wichtig dass man sich das einmal klar macht dass es nicht so ist wenn ich einmal in dem
22:40 akzeptierenden zustand bin dann hört es auf sondern das kann auch weiter gehen und gucken wir mal genau so und ich habe jetzt hier noch mal irgendwie zwei
22:52 beispiel um das ein bisschen klarer zu machen also hier haben wir jetzt wieder sehen wir einfach einen automaten der hierhin gemalt ist und jetzt kann man
23:00 und die frage ist jetzt und es wird uns die nächsten vorlesung in so ein bisschen beschäftigen wie sehen denn jetzt die sprachen aus die von einem
23:06 automaten akzeptiert werden und in diesem falle kann man damit jetzt ein bisschen rum spielen wie macht man das also guckt sich halt mal verschiedene
23:14 wörter an und schaut immer was passiert welche wörter werden akzeptiert welche werden nicht akzeptiert und man kann ich habe hier einfach mal ein paar beispiele
23:20 hingeschrieben aber das können sie gerne auch selber machen also denken sie sich einfach folgen von nullen und einsen aus und probieren sie aus wo sie dann landen
23:29 und er soll hier sind ein paar beispiele also mit diesem wort zum beispiel lampen wir in q2 das heißt es wird wird akzeptiert mit diesem wort irland nur in
23:37 q1 das ist kein akzeptieren dazu stand und jetzt kann man da ein bisschen rum spielen und was man dann herausfinden wird zumindest intuitiv ist dass die
23:46 sprache die von diesem automaten akzeptiert wird es sind genau die worte der letzte buchstabe 1 ist also wenn ich ein wort habt und der letzte buchstabe
23:54 ist eins dann wird es akzeptiert und wenn der letzte buchstabe 0 ist dann wird das wort nicht akzeptiert so das können sie sich vielleicht zu hause ein
24:03 bisschen anschauen ob sie das glauben ich glaube in dem automat ist es relativ einfach zu sehen und man kann jetzt auch den gleichen automat nehmen und zum
24:10 beispiel den anderen den ersten zustand als akzeptierenden zustand machen und was dann passiert ist kann man jetzt wiederum spielen also bei normalen
24:20 worten würde man sagen die wörter müssen jetzt einfach in einer 0 endstand 1 1 und dann akzeptiert das ding ist oder es könnte aber auch sein also dass das
24:29 leere wort passiert weil er weil ich bin im staat zustande wenn der staat zustand schon akzeptieren das heißt es wenn ich nichts gelesen habe bin ich auch in dem
24:36 akzeptierenden zustand das heißt insbesondere das leere wort wurde auch akzeptiert das heißt es ist element von dieser sprache
24:48 so jetzt kommt noch eine letzte definition in seinem zimmer mit den definitionen für die automaten auch erst mal durch und zwar hat die erweiterte
24:55 übergangs funktion also was wir bisher gemacht haben ist in der übergangs fraktion haben wir immer einzelne buchstaben hingeschrieben und manchmal
25:02 wird es für später einfacher sein wenn man sagen kann was ist denn der übergang wenn ich den zustand 1 bin und ich lese die buchstaben 001 und dann muss ich
25:11 halt gucken welches sind die welche folge müsste hier entlang gehen und ich definiere dann praktisch die übergangs funktion auch für wörter und das ist das
25:19 was jetzt hier passiert ist und wir schauen uns das einfach anders ist aber auch nichts besonders kompliziert ist also wir fangen an wir haben die normale
25:27 übergangs funktion als es sei delta von coo der delta die funktion den zustand nimmt mit buchstaben nimmt und wieder in den zustand aus flugzeit es eine
25:36 überwachungsfunktion wie sie halt in automaten definiert ist und jetzt definieren wir die sogenannte erweiterte übergangs funktion und die halt stelter
25:44 stern was einfach mit einem sternchen oben dran und der unterschied ist jetzt dass es in dem viele ein zustand aber die
25:52 eingabe kann jetzt ein beliebiges wort aus kufstein auf sigma stern sein und sie enden aber wieder in den zustand und wir definiert ist jetzt induktiv das
26:02 heißt wir schreiten vielleicht schauen was uns erst mal an sich sagt dann gleich noch was dazu also wir definieren zuerst mal was ist delta stern also die
26:10 wir hier dass es dieses wort was wir lesen ist in sigmas stern sieht man stern könnte das leere wort sein das sollten wir zuerst gucken also wenn wir
26:19 den zustand sind und das leere wort lesen sagen wir einfach wir bleiben in dem zustand und zwar für egal was kurs also für alle coolen unserer zustands
26:27 menge wird es so definiert und dann setzen wir jetzt haben wir nicht lehrer wort gelesen jetzt setzen wir
26:36 [Musik] und jetzt wollen wir uns anschauen was passiert denn wenn ich den übergang nach für ein wort und noch hinten dran gehen
26:47 ich will so eine art induktive definition haben sie nehmen jetzt irgendein wort wir nehmen dann wir wüssten schon was
26:52 passiert wenn wenn ich ein wort veliz und dann wollen wir wissen was würde passieren wenn ich das wort weh und noch eine a hintendran lesen würde
27:01 und jetzt definieren wir einfach das muss man sich jetzt bisschen angucken also was ist jetzt diese neue übergangs funktion ich bin den zustand kuh und
27:08 lesen na ja und was machen wir jetzt wir sagen na ja das ist halt erstmal ich bin ich stand im zustand kuhn liest das wort wie das ist dieser teil der endlich in
27:22 dem zustand also das ist die ausgabe von diesem ding nach diesen von wesen zustand und jetzt lese ich noch obendrauf
27:29 und das ist jetzt die übergang und zwar die normale übergangs funktion jetzt habe ich einen bestimmten zustand und lesen buchstaben und dann kommt wieder
27:35 neuer zustand raus und das wird durch delta definiert das heißt es ist eine induktive des ok und so denken wir noch mal wir definieren jetzt was passiert
27:46 wenn ich das wort w mit dem and buchstaben w und dann dennoch den buchstaben a drangehängt pack und wer was ist davon die übergangs funktion
27:54 gelesen also erst w neben induktiv anders das ding schon definiert ist und dann lesen wir noch dazu und das können wir eben durch die gegebene übergangs zu
28:02 machen so und warum macht so eine definition jetzt sind als dass sie müssen jetzt noch mal vielleicht an induktion zurückdenken das wird uns
28:10 jetzt ganz oft begegnen im übrigen also induktion funktioniert immer so gerne induktions anfang der und oft in mathematik sind auf die induktion über
28:19 die länge also über über eine natürliche zahl wir könnten wir zum beispiel sagen wir machen induktion über die länge des wortes wir fangen an bord länge 0 und
28:28 definieren was passiert bei vox länge 0 das ist nämlich genau das was ich hier gemacht habe bei ordnung null bleiben wo wir sind
28:33 das ist was in den beweis der induktions anfang wäre jetzt käme in den beweis die induktions annahmen wir nehmen an haben schon für alle längen ab bis zu m
28:42 haben wir schon definiert was passieren soll ich habe das jetzt hier gar nicht so explizit hin geschrieben also sagen wir
28:48 mal bis wort länge m haben wir es definiert also wir wissen und sagen wir mal das wort wie hier hat längen und dann wissen wir schon was die übergangs
28:54 funktion ist und jetzt wollen wir wissen was ist denn die übergangs funktion wenn ich ein wort der länge endlos 1 ab und das ist genau das was in dieser
29:01 definition passiert also wort wer hat länge m 1 buchstabe dran dann hat das ganze ding menge einfluss 1 wir sagen halt also das
29:09 ist erstmal gucken wir was wissen wir denn schon über das wort mit der länge m da nehmen wir an wir wüssten schon das hätten wir schon definiert
29:16 na ja und jetzt kommt eine normale übergang nur durch einen buchstaben definiert durch dieses zustande so und auf diese weise und sie können das jetzt
29:25 auch mal durch ein beispiel sich überlegen vielleicht von den automaten von der vorigen folie wie dieses wie diese funktion delta stern aussieht also
29:32 wir eben haben es für y definiert und jetzt können wir durch dieses induktions schritt sagen na ja was passiert denn jetzt wenn apps i lon also wenn wir
29:40 jetzt zum beispiel nur einen buchstaben lesen länge 1 na ja dann würden wir diese definition jetzt hier ausrufen denn wer nur einen buchstaben lesen dann
29:48 wäre dieses wort wer das leere wort und ein buchstabe für das leere wort wissen wir schon das haben wir schon definierter land rover vorher schon
29:56 waren und dann kommt er eine buchstabe da machen wir den normalen übergang auf diese weise kriegen wir würden wir jetzt
30:02 rauskriegen das delta stern von den zustand kuh und nur einem buchstaben ja ich das gleiche ist wie delta von dieses mal in buchstaben und jetzt kann man
30:12 sich angucken was passiert mit zwei buchstaben wir wissen schon was passieren mit einem buchstaben und jetzt machen wir dieses konstrukt für zwei
30:17 buchstaben und dann für drei und vier 4 und so weiter und auf diese weise können wir für beliebige worte definieren was ist diese übergangs funktion delta stern
30:25 ich glaube intuitives das total klar was man da passiert wenn man sich dieses bild vom automaten anschauen dann guck mal mit mit dem wort wie komme ich von
30:33 dem einen zustand und ich lese das wort in welchem zustand lande ich dann was hier an der stelle vielleicht wichtig ist zu verstehen wie diese formale art
30:40 es aufzuschreiben funktioniert und dieses induktive argument dass man auf diese weise was definieren kann denn das ist vielleicht was was sie
30:46 jetzt noch nicht so oft gesehen haben was uns aber jetzt sehr oft begegnen wird ja und damit haben wir jetzt die
30:54 endlichen automaten erstmal definiert wir haben gesehen was die sind was die für zutaten haben die übergangs funktion und so weiter und in der nächsten
31:00 vorlesung schauen wir uns dann an welche sprache oder schauen wir uns sprachen an die von solchen automaten definiert werden und was für eigenschaften die
31:07 haben