Informatik Oberstufe: Endliche Automaten 4 - Grenzen
Frank Röhr
https://www.youtube.com/watch?v=rd61BsNcyW4

Transkript (automatisch erstellt)

0:01 [Musik] [Musik] hallo seid gegrüßt bei lahm ist frank
0:17 und ich möchte euch heute ein wenig über ein problem zeigen was ein endlicher automat nicht lösen kann ja also die grenzen von endlichen automaten ja die
0:27 letzten mal das schon gesehen dass wir endlich wörter natürlich erkennen können und auch etliche sprachen und wir können auch bestimmte muster in sprachen
0:35 erkennen wir können es noch hatten am anfang mal alles was mit abe beginnt und endet oder was irgendwo ab drin stehen hat und was damit beendet konnte der
0:43 erste automat erkennen wo was geht immer wieder abs kann man erkennen man kann auch erkennen so was wie hier sind über 2 ws und beim a oder man kann auch ein
0:51 bisschen komplexer sachen machen ich möchte jetzt heute noch was anderes machen ich möchte jetzt heute mal die sprache
0:56 und vom automaten erkennen lassen die gleich bieten wie alle wörter enthält die gleich viele gewesen halten ja also vielleicht wieder arzt gewesen
1:06 das möchte so wenn ihm eine flasche wein machen das x mark i und sagt gleich gemacht gleich wie ok ich nehme nur a und b r
1:22 zeigen dass das mal hier hin dass man schon überlegt jetzt überlege ich mir ich will jetzt wissen kommt nun aber kommt ein b erstmal bin ich gleich viele
1:34 hab erstmal kann ich dann sagen entweder das leere wort das ruhig was neues das hatten wir noch nicht
1:47 nämlich das wort das gütezeichen enthält das müsste auch akzeptieren dann hätten mich gleich viele azubis wenn ich gar keine mich 0 von beiden so
1:54 das heißt der staat zu stellen ist gleichzeitig im endzustand es gibt keine regel gesagt dass das nicht geht dann sein dann wird auch das leere wort
2:01 akzeptiert so jetzt wie wir aber mal medias res und sagen weil wir machen danach was soll man natürlich nicht akzeptieren aber wenn wir jetzt ein weg
2:09 kommt dann die mir zurück war das wie hier in wien kanal immer zurück okay aber wurde jetzt akzeptieren wie aber noch nicht wie also natürlich
2:21 auch akzeptieren wahrnehmen jetzt soll das war schon richtig weil wir es wahrhaben wiederum schon definiert und wir gehen zurück mit einem paar bba
2:33 würde jetzt akzeptieren hat ja auch gleich viele punkte wie bse super funktioniert hat das problem ist nur wenn ich jetzt zwei es habe direkt am
2:41 anfang und radwegen abb habe jetzt gar nicht definiert aber wir haben ja die regel was mich definiert es landet im kriegszustand das heißt das würde er
2:48 jetzt nicht akzeptieren nicht nur was zu lassen also nehmen wir jetzt mal noch einen zustand dazu hier wird schon nah kommt
2:54 eine noch nachkommen so und zurück würden wir dann hier ein baby selbe spielchen würde ich jetzt hier unten machen
3:06 ihr müsst jetzt das wie kommen genau und dann könnte zurück das pendant zu machen so prima jetzt könnte ich auch so was machen wie abb wwa würde auch
3:19 akzeptieren hat gleich viele sbb es ja welches drei es am anfang habe er trotzdem sein dass das wort praktiziert werden muss können ihre drei babys
3:27 kommen ihr seht schon ich müsste jetzt machen zustand rüber und einen runter machen usw
3:33 das mache ich jetzt nicht jetzt an der stelle einfach mal auf ich habe ich nur so viel das geht nicht ich kann nicht allgemein den automaten
3:41 bauen der erkennt ob die sprache gleich viele arzt ob ein wort gleich viele babys ab also die sprache die aus allen wörtern
3:50 aus ag besteht die gleich viele sbbs haben kann ein endlicher automatisch erkennen warum ist das so hier könnte mal kurz zu verlegen das
3:59 kann ja vielleicht ganz anders machen als ich das hier gemacht habe so ein automat versucht das ja irgendwie auch merkwürdige anwalt zu machen vielleicht
4:06 gibt's ja was sie schlauer das ist das was ich gemacht habe könnte ein kurzvideo anhalten weil überlegen warum das nicht geht und da verrate ich euch
4:15 so jetzt davon aus dass wir alle verlegt habe warum es nicht geht der grund ist erstmal sehr simpel ein endlicher automat hat endlich viele
4:23 zustände dh ich hab hier bis von mokono bis kopiert und zustände ich kann es natürlich beliebig viele
4:29 nehmen ich hätte auch 100 nehmen aber irgendwo ist eine grenze denn der endlich automat hat nun endlich viele der ist nicht unendlich automat nämlich
4:37 automat hat man endlich viele und wenn ich jetzt meinetwegen ich sage mal wir sagen wir haben einen automaten der diese sprache erkennt dieser automat hat
4:46 irgend einer anzahl von zuständen immer 100 gerade bei den anderen 100 und sag ich jetzt mal das wort das aus 100 und einem a besteht wenn ich diesen
4:56 automaten jetzt war auf loslasse auch das wort das aus 101 a und dann 100 als b natürlich 101 101 ni denn das wort dass daraus besteht darauf
5:07 loslasse dann musste er einen zustand während er die ars abarbeitet mindestens einen zustand zweimal erreichen
5:18 er hat 100 zustände ich hatte aber 101 das heißt ein zustand kommt irgendwann doppelt vor ich bin jetzt auch anfang sein dass keine schleife sein
5:29 das kann auch irgendwie im kreis laufen aber irgendwann muss das muss das 2 mal vorgekommen sein denn der zustand und den bereich dass du
5:36 da ist einfach vom arzt zwischen diese art kann ich dann einfach zweimal leben und er würde wieder genauso laufen der automat noch immer dasselbe wenn wir das
5:48 an bord erkennen was mehr als als bs hat so das kann man noch mal formalisieren im sogenannten pumping lämmer das kommt auch noch
5:56 aber das wird erstmal nur zur veranschaulichung warum man endlich automatik grenzen hat und der computer der frau ist entsteht mit denen gerade
6:04 dieses video pocht das handy oder was auch immer das ist das kann auf jeden fall ist das kein problem von dem etwas erfahrene programmierer ein programm zu
6:12 schreiben wo ihr ein wort aus aasen bs ein gibt auch quasi beliebig lang und was daneben die asn dbs zählten sagt und das gleich viele sind ja also es kein
6:21 problem ist der computer für euch nicht lösen kann es ist aber ein problem was unendliche automatisch lösen kann
6:26 dazu kommt man später noch mal mehr