47. Video Theoretische Informatik WS 13/14 - Konstruktion DEA aus regulären Ausdruck - unistreams
Unistreams
https://www.youtube.com/watch?v=8sEWyngaXlM

Transkript (automatisch erstellt)

0:02 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
0:13 ausdrücken die beschreiben jetzt wieder eine sprach klasse jetzt haben wir definiert oder vereinbart als die sprach klasse eeg für
0:21 die reguläre sprach klasse noch was sonst heute überlegen wollen ist den zusammenhang dass wenn ich beispielsweise einen regulären ausdruck
0:30 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
0:38 endlicher automat und der folgenden eigenschaft dass die sprache identisch ist und umgekehrt
0:48 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
0:58 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
1:14 zusammenhang wollen wir hier stellen die eine richtung ist ganz leicht die andere richtung ist ein bisschen schwieriger die ist vor allem ein
1:24 bisschen technisch wir fangen wir mit zum einführenden beispiel an und zwar
1:31 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
1:40 automaten dazu konstruieren ein beispiel dazu an neben einfach mal einen regulären ausdruck her das habe ich hier
1:51 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
2:03 mir anschauen die einzelnen operationen in diesem fall habe ich ja eigentlich alle drei operatoren mit denen wir reguläre ausdrücke bilden
2:12 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
2:22 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
2:29 drin wir können automaten konstruieren für die lehre menge wir können automaten konstruieren für das leere wort wir
2:36 können automaten konstruieren für ein einzelnes zeichen und wenn wir das jetzt irgendwie uns überlegen wie wir sozusagen diese operatoren als automaten
2:45 abbilden dann haben wir ja eh schon alles fertig weil dann haben wir endlich alles das berücksichtigt was reguläre ausdrücke
2:55 ausmacht wenn man das haben wir das verstanden haben aber quasi die einrichtung jetzt beweise ist schon geführt
3:02 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
3:13 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
3:23 den kanten dran stehen haben und welche zustände finale sind ja wenn man a b verarbeiten wollen der zugehörige automat habe
3:32 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
3:45 kombination die wir hier haben hier natürlich auch hier habe sich das nicht noch mal an gegeben das haben wir quasi das ist
3:53 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
4:05 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
4:14 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
4:24 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
4:33 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
4:40 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
4:50 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
5:03 uns entweder entscheiden sind im staat zustand und wir können uns entweder entscheiden wir gehen nach oben oder nach unten so
5:12 dass gegen das können wir jetzt sogar noch dadurch vereinfachen dass wir sagen na ja rein zufällig machen sozusagen die konstruktion
5:20 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
5:30 können den auch ganz leicht überführen in den folgenden automaten das passt ja nicht da fehlt mir jetzt irgendwas fehlt noch
5:38 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
5:50 gemacht haben also auch den plus apparat uhr können wir realisieren genau so und jetzt müssen wir doch jetzt
5:59 haben wir sozusagen die koordination ist irgendwie ganz einfach die den fluss apparat uhr können wir uns noch überlegen wir was
6:08 mit dem stern operator machen auch das haben wir uns glaube ich in dem ein beispiel schon mal überlegt stern heißt ja
6:17 einmal drei mal oder beliebig oft das einmal machen würden das mache ich jetzt mal sollen noch mal in rot also jetzt
6:26 irgendwie stern operator ziehen wir einfach eine kante zurück anstatt von den finalen von beiden finalen zuständen
6:37 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
6:46 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
6:56 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
7:03 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
7:09 irgendwen automaten das ist aber auch gar nicht schwierig so die können wir jetzt auch eliminieren ja
7:27 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
7:37 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
7:46 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
7:53 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
8:00 haben wir formal völlig allgemein bewiesen so an diesem konkreten beispiel wie sieht das aus was war die konstruktion für diese endlichen
8:08 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
8:18 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
8:26 beispiel heißen ich würde das so machen und die dafür streichen die brauche ich nämlich gar nicht mehr
8:36 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
8:47 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
8:56 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
9:06 ist kein der ist ja nicht warum es keinen dr zwei stellen einmal das was sie gerade sagten ich komme von dem
9:19 wenn ich hier in belize dann mache ich irgendwie so nicht nennen wir ihn mal cueff und dann wollte ich noch das problem
9:26 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
9:34 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
9:43 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
9:53 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
10:01 wir noch auflösen das soll jetzt da müssen wir uns mal anschauen vom zustand 0
10:09 wir bräuchten einen zustand 12 ich habe den zustand 0
10:19 da komme ich mit dem hin musste von 12 von 1 mit einem b komme ich zu null gehen von 2 mb komme ich
10:29 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
10:43 zu 12 hin von der wirklichen unheimlich man sieht dass das wird die 12 koev da kann ich
10:58 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
11:04 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
11:11 wirklich alle zustände das wird ein größeres dinge okay so aber prinzipiell also die wesentlichen ideen stecken eigentlich
11:21 hier drin was sind die wesentlichen operatoren für die bildung eines regulären ausdrucks ja das ist die kombination
11:31 da wissen wir wie das mit dem automaten funktioniert der plus operator das haben uns angeguckt und den sternen parat haben uns auch an