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
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