21. Video Theoretische Informatik WS 2013/14 - Beispiel: endlicher Automat - unistreams
Unistreams
https://www.youtube.com/watch?v=X-eYboseR0g

Transkript (automatisch erstellt)

0:04 wir nehmen jetzt den folgenden automaten die zustands menge q1 q2 als zeichen der eingabe haben wir klein klein b dann haben wir delta wie folgt
0:21 gleich definiert wir haben den start zustand kuh 0 und wir haben die menge der finalen zustände das ist ebenfalls der zustand kuh 0 so und delta ist wie
0:33 folgt definiert ich kann das beispielsweise in einer tabelle hin mal so
0:40 im zustand 0 lese ich ein a und dann komme ich in den zustand q1 eben kuh stand zu stand kuno lese ich ein b dann komme ich in den zustand q2
0:54 im zustand q1 lese ich ein aber dann komme ich wieder nach koh 0 wie komme ich nach q2 so was mache ich jetzt mit so nem
1:08 mit zum automaten mit dem automaten kann ich jetzt rechnen so hatte ich ja gesagt den nutzen war um zu überprüfen ob ein wort eine bestimmte
1:19 eigenschaft hat und ich führe einfach mal so eine rechnung durch und dann kommen wir gleich dazu was noch weiter dahinter steckt
1:30 also eine rechnung in a besteht dann aus der anwendung der übergangs funktion falls wir neben dem wort beispielsweise die eingabe
1:42 sei aber so dann hörten wir jetzt als erstes im wir sind im staat zustand kuno ja das war ja mein start zustand
1:55 dann haben wir unsere eingabe ja so cook in einer tabelle nach da liefert mir das delta ist gerade q1 da ist der automat ließ das a und
2:13 wechselt in den zustand q1 dem zustand q1 lesen wir jetzt noch ein paar das erst zweite
2:25 gucke ich auch wieder minor traveller nach q1 a dann lande ich wieder in kunow wenn ich in como bin und das dritte zeichen lesen das ist das
2:35 b auch wieder mal nachgeguckt kuh 0 b ist co2 das ist jetzt etwas mühselig so hin zu schreiben darum
2:46 vereinbaren war das folgende das war auch so was machen können dass ich nicht nur ein einzelnes zeichen in diese übergangs funktion reinstecken
2:55 kann sondern auch ein ganzes wort und um das eindeutig zu kennzeichnen mache ich meistens und sternchen hier oben dran das heißt ich werde jetzt
3:04 diese übergangs funktion nicht nur einfach an sondern ich werde gleich mehrfach an und das erklären wo eigentlich wie vor einfach wie folgt
3:11 wir gehen einfach schrittweise durch delta von der eigentlich muss ich es formal sauber definieren das mache ich gerade
3:26 und zwar so wie erweitern die jetzt von delta auf delta stern und zwar wie folgt wir erklären delta stern für einen
3:37 beliebigen zustand y das sei gleich das heißt wenn ich nichts lesen bleibt der zwischen einfach erhalten und delta stern von ich bin in einem zustand habe
3:52 ein wort bestehend aus w also irgendwie folge von zeichen und dann ein einzelnes symbol das ist gerade delta von also wir erklären dass auch induktiv
4:04 ich ziehe quasi einmal dieses hier raus und damit bröselig hier sozusagen die ist delta stern auf in zwei anwendungen hier und bin ich ja sozusagen durchmache
4:15 das mache ich jetzt am ein beispiel das wäre also delta von delta stern hu 0,3 das ist sozusagen diese anwendung jetzt hier dieser induktiven definition
4:31 von delta stern auf das akw das ist das gleiche wie delta von delta von
4:51 0,8 ist jetzt sozusagen auseinander dass ich das zurückführen auf die anwendung von delta auf einzelne zeichen so das ist gleich delta von delta von
5:02 delta kuh 0,3 so und jetzt kann ich das hin aufschreiben
5:13 können uns unsere tabelle wieder nachgucken das q1 q1
5:22 wieder cool und delta von courbet das war gerade co2 also jetzt haben wir sozusagen die übergangs
5:32 funktion ergänzt oder erweitert von einem einzelnen symbol auf ganze wörter