Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
47. Video Theoretische Informatik WS 13/14 - Konstruktion DEA aus regulären Ausdruck - unistreams
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 73 Zeilen
- ich möchte den zusammenhang herstellen einmal zwischen den rationalen sprachen und den regulären sprachen ja auch werden ja gesagt die alle regulären
- ausdrücken die beschreiben jetzt wieder eine sprach klasse jetzt haben wir definiert oder vereinbart als die sprach klasse eeg für
- die reguläre sprach klasse noch was sonst heute überlegen wollen ist den zusammenhang dass wenn ich beispielsweise einen regulären ausdruck
- habe das ist dann immer einen automaten gibt ja dann existiert immer ein automat ich nenne ihn jetzt mal und naja das ist dann irgendwie ein deterministische
- endlicher automat und der folgenden eigenschaft dass die sprache identisch ist und umgekehrt
- 2000 das überlegen wollen ist quasi die andere richtung das wenn ich einen beliebigen endlichen automaten habe das ist dann auch ein regulären ausdruck
- gibt denen ich jetzt mal eher kleine entschuldigung da muss natürlich hier der stehen das dann halt auch gilt 11h ist gleich elf ja- und nahm er den
- zusammenhang wollen wir hier stellen die eine richtung ist ganz leicht die andere richtung ist ein bisschen schwieriger die ist vor allem ein
- bisschen technisch wir fangen wir mit zum einführenden beispiel an und zwar
- dass wir ausgehend von einem wir gucken uns quasi hier erstmal diese richtung an diese richtung wir haben quasi einen regulären ausdruck und wie können wir ja
- automaten dazu konstruieren ein beispiel dazu an neben einfach mal einen regulären ausdruck her das habe ich hier
- bkw um das ganze im wege stand so wie konstruieren automaten dazu ich muss mir einfach diesen regulären ausdruck angucken und da im wesentlichen muss ich
- mir anschauen die einzelnen operationen in diesem fall habe ich ja eigentlich alle drei operatoren mit denen wir reguläre ausdrücke bilden
- können die habe ich ja hier ich habe hier einmal die kontamination ja ich habe an dieser stelle in den plus operator und ich hab
- halt hier den stern operator und damit habe ich halt das wesentliche eigentlich schon was so ein regulären ausgebildet habe ich ja sozusagen alles schon mit
- drin wir können automaten konstruieren für die lehre menge wir können automaten konstruieren für das leere wort wir
- können automaten konstruieren für ein einzelnes zeichen und wenn wir das jetzt irgendwie uns überlegen wie wir sozusagen diese operatoren als automaten
- abbilden dann haben wir ja eh schon alles fertig weil dann haben wir endlich alles das berücksichtigt was reguläre ausdrücke
- ausmacht wenn man das haben wir das verstanden haben aber quasi die einrichtung jetzt beweise ist schon geführt
- da machen wir das mal konkrete nation das heißt ich habe wie sieht ein automat aus für abi ist ganz einfach nur das ist das können
- wir schon wir fangen einfach mit einem zustand an wie die zustände jetzt heißen ist völlig egal ja das wissen das kommt letztendlich immer darauf an was war an
- den kanten dran stehen haben und welche zustände finale sind ja wenn man a b verarbeiten wollen der zugehörige automat habe
- schon einmal automarken für das gleiche können wir jetzt machen für navi schreiben wir einfach dran also zu sagen diese beiden teile mit der
- kombination die wir hier haben hier natürlich auch hier habe sich das nicht noch mal an gegeben das haben wir quasi das ist
- ganz leicht so gucken uns den nächsten operator an der präparator heißt ja entweder das eine oder das andere auch das können
- wir bei seinem automaten ganz einfach machen wir nehmen den einfach weg das mache ich mal mit blau dass man unterschied sieht man jetzt mal hier
- sozusagen gegen den plus operator ich meine im blau ja dann machen wir einfach neuen staates zustand schreiben exelon dran was dürfen uns natürlich nicht
- irritiert sein weil ich hatte ja vorher gesagt es gibt zu jedem regulären ausdruck gibt es um endlich ein automat und ich habe den
- hier als dea gekennzeichnet das ist natürlich jetzt kein dhea wurden epson konnte drin haben aber was war schon gelernt haben in irgendeinem satz den
- ich ihnen bewiesen habe ja das war das was wir herausbekommen ja das war das in der um formen können nun ganz offensichtlich dieser automat
- der akzeptiert jetzt genau die sprache die hier drin steht also entweder a b oder a b das heißt dann andere möglichkeiten haben wir nicht wir können
- uns entweder entscheiden sind im staat zustand und wir können uns entweder entscheiden wir gehen nach oben oder nach unten so
- dass gegen das können wir jetzt sogar noch dadurch vereinfachen dass wir sagen na ja rein zufällig machen sozusagen die konstruktion
- die wahl bei den beweis geführt haben vorgenommen haben dass wir diese epson kanten eliminieren der hat jetzt hier zweimal das a dran stehen das heißt wir
- können den auch ganz leicht überführen in den folgenden automaten das passt ja nicht da fehlt mir jetzt irgendwas fehlt noch
- das bild war also diesen tech wollen das ist sozusagen genau das angewendet was war im rahmen des nachweises dass y diaz sich auch als der darstellen lassen oder
- gemacht haben also auch den plus apparat uhr können wir realisieren genau so und jetzt müssen wir doch jetzt
- haben wir sozusagen die koordination ist irgendwie ganz einfach die den fluss apparat uhr können wir uns noch überlegen wir was
- mit dem stern operator machen auch das haben wir uns glaube ich in dem ein beispiel schon mal überlegt stern heißt ja
- einmal drei mal oder beliebig oft das einmal machen würden das mache ich jetzt mal sollen noch mal in rot also jetzt
- irgendwie stern operator ziehen wir einfach eine kante zurück anstatt von den finalen von beiden finalen zuständen
- hören wir müssen noch den fall erschlagen dass wir sozusagen kein mal hier durchlaufen das heißt wir müssen den staat zustand final machen
- weil ich damals einen kringel rein und wir schon fertig das heißt der hand des beispiels sehen sie das ist eigentlich gar nicht so gar
- nicht so schwierig ich habe mir zwar noch null gedanken gemacht zu unserer gemeinsamen prüfung die wir ja irgendwie bewerkstelligen dürfen aber ich kann
- mich einmal der mündlichen prüfung erinnern und zum beispiel hab ich immer abgefragt wollte immer wissen auch wie macht man aus dem ring oder ein ausdruck
- irgendwen automaten das ist aber auch gar nicht schwierig so die können wir jetzt auch eliminieren ja
- das ist nicht notwendig also wenn das wissen wir dass das geht das noch mal bewiesen was gilt für alle beispiele und jetzt ganz konkret in diesem
- beispiel da müssen wir den automaten ein bisschen umbauen können wir ja mal probieren ob ich das jetzt so hinkriege ich mal ich lasse dich mal da stehe ich
- mal den einfach noch mal hierhin dann male ich da mal so ein bisschen dran rum und das ist genau das was wir in der theoretische informatik so spaß macht
- das ist so anschaulich jetzt kann man also ein bisschen rumtüfteln ein bisschen rumbasteln ich mal hier einfach noch mal hin also das geht immer und das
- haben wir formal völlig allgemein bewiesen so an diesem konkreten beispiel wie sieht das aus was war die konstruktion für diese endlichen
- automaten für diese y kannten so man guckt sich entweder die kante an die quasi zu einem zustand hin führt von dem aus eine epson
- kannte losläuft ja und führt diese kannte dann sozusagen zu direkt zu dem zustand zu dem auch die epson kannte führt zwar ist das würde in diesem
- beispiel heißen ich würde das so machen und die dafür streichen die brauche ich nämlich gar nicht mehr
- den hätte ich auch final das heißt ich kann jetzt sozusagen einmal hier rumlaufen abb aw und hier im prinzip genauso hätten wir jetzt die y kannte ja
- die würde ich jetzt streichen weil ich führe direkt diese kannte die kante mit einem b für ich direkt auf den staat zustand das heißt
- die macher weg wir würden man hier einfach die kante hinlegen und dann wäre das der entsprechende dafür dass mal gucken haben wir nie das
- ist kein der ist ja nicht warum es keinen dr zwei stellen einmal das was sie gerade sagten ich komme von dem
- wenn ich hier in belize dann mache ich irgendwie so nicht nennen wir ihn mal cueff und dann wollte ich noch das problem
- dass wir hier von dem aus zwei mal loslaufen können das dürfen wir auch nicht jetzt heißt das müsste jetzt müssen wir
- diese potenz mengen konstruktion machen ich müsste die hier irgendwie benennen der kleine krieger dar in der sich jetzt für 0 ich habe ihn jetzt benannt ja ja
- ja der heißt eins der heißt 2 wir würden hier müsste man fehler zustande noch überführen der wird jetzt unhandlich hier sieht man so wie
- handlich diese nicht deterministisch in automaten sind b das ist okay hier geht keiner weg den müssen wir dran machen und das müssen
- wir noch auflösen das soll jetzt da müssen wir uns mal anschauen vom zustand 0
- wir bräuchten einen zustand 12 ich habe den zustand 0
- da komme ich mit dem hin musste von 12 von 1 mit einem b komme ich zu null gehen von 2 mb komme ich
- dahin das heißt hier kann man von 12 ma komme ich zum cueff und man komme ich zum zustand 30 mit mama komm ich
- zu 12 hin von der wirklichen unheimlich man sieht dass das wird die 12 koev da kann ich
- bin jetzt schon durcheinander geraten genügt ihnen das als andeutung das müsste ich jetzt an der tafel machen damit ich müsste ich mir auch nicht
- aufschreiben was wird man sieht hier vielleicht noch mal schön den vorteil von diesen nicht der minister schon automaten ja aber ich muss jetzt
- wirklich alle zustände das wird ein größeres dinge okay so aber prinzipiell also die wesentlichen ideen stecken eigentlich
- hier drin was sind die wesentlichen operatoren für die bildung eines regulären ausdrucks ja das ist die kombination
- da wissen wir wie das mit dem automaten funktioniert der plus operator das haben uns angeguckt und den sternen parat haben uns auch an
Zum Nachlesen
Nichtdeterministischer endlicher AutomatEin nichtdeterministischer endlicher Automat (NEA; englisch nondeterministic finite automaton, NFA) ist ein endlicher Automat, bei dem es für den …
Regulärer AusdruckEin regulärer Ausdruck (englisch regular expression, Abkürzung RegExp oder Regex) ist in der theoretischen Informatik eine Zeichenkette, …
Reguläre SpracheIn der theoretischen Informatik ist eine reguläre Sprache oder reguläre Menge oder erkennbare Sprache eine formale Sprache, die einigen Einschränkungen …
PotenzautomatEin endlicher Automat A heißt Potenzautomat des endlichen Automaten B, wenn seine Zustandsmenge gerade die Potenzmenge der Zustandsmenge von B ist. Formal …