Bestand wählen
Merken

13A.1 Formale Sprachen, reguläre Ausdrücke, endliche Automaten, Pumping-Lemma

Zitierlink des Filmsegments
Embed Code

Automatisierte Medienanalyse

Beta
Erkannte Entitäten
Sprachtranskript
So die letzten Wochen ist ist das soll einen Rundgang durch die Informatik sein ansatzweise erzählt was Datenstrukturen sind die ist eine Informatik man das komplette macht so was wie Warteschlangen und Stack erhalten das als Mensch wächst auch nach mäßiger natürlich genauso zu uns sagt man auch dann ansatzweise mal was zu einer wird man insbesondere Sortierverfahren mit
Das ist auch ein Thema mit dem man sich ein oder mehrere Semester auseinandersetzen Bergermann ist etwas tiefsinniger machen wir uns heute möchte ich einmal der nochmal durch die formalen Sprachen Sprachen und parallel dazu etwas das anscheinend nichts zu tun hat aber lustigerweise doch sehr viel damit zu tun hat die endlichen Automaten endlicher Automat das ist ein ziemlich listiges Thema der theoretischen Informatik Informatik an einer Uni studieren wenn sie der Nanos mit gequält haben abstrakte Geschichte aber andererseits glaube derzeit den ich heute wird dann auch eine sehr praktische Geschichte die man dann doch für sehr viele Sachen verwenden kann
Eine formale Sprache in der Informatik
So einfach eine Sammlung von Zeichenketten sei formale Sprache und seine Sammlung von Zeichenketten als Zeichenketten die erlaubt sind die gültig sind in dieser Sprache die korrekt sind dieser sprach und sonst keine Zeichenketten wollte mit Ihnen gleich zum Beispiel Telefonnummern ankucken die formale Sprache die aus aller welcher was auch immer korrekt gebildeten Telefonnummern besteht zum Beispiel 0 1 2 3 4 5 6 und so eine gebildete Telefonnummer sein ebenso soll 0 5 2 allerdings 1 2 3 6 gebildet Telefonnummer sei das wäre die Sprache der korrekte bildeten Telefonnummern was nicht dabei ist so schreiben Telefonnummer die nicht durchgestrichen sich das So schreiben als klar zu lesen ist durchgestrichen ein die nicht dabei als wäre zum Beispiel 110 Geschenke nicht nur an und hat kein / /S r E: k S t r I C/ Sollte also nicht von allgemeinen Telefonnummern werden sondern sollten von Telefonnummern für die man als normaler Mensch gegen das man nicht die sondern nur von dieser und / /S r E: k S t r I C/ die Zahl nach dem / /S r E: k S t r I C/ soll keine 0 haben am Anfang Usw. Das müsse man jetzt mal formalisieren dass das was ich mir unter dieser Sprache vorstellen die Sprache der gebildeten Telefonnummer für normale Leute einer formalen Sprachen der dann in allen der gebildeten Webseiten HTML-Code die 1. Greg gewählt Seite die 2. usw. Es gibt unendlich viele direkt den derzeit 2 der große Sprache die Sprache die aus einem gebildeten C-Programmen stehe ich finde als Zeichenkette ein komplettes Programm das nächste komplette C-Programm usw. usw. bis es sich das alle Geräte gebildeten C-Programme aufgelistet auch das wäre eine formale Sprache und Informatik wo man sie einfach nur an diese Zeichenketten gebildet werden kann ich das Regeln fassen solche Zeichenketten zu bilden gibt es verschiedene Sorten an Komplexität bei diesen was folgt aus dem wegen was kann ich direkt ableiten und tief in die Sprache reingeguckt zu haben so was kann sich ein es geht also um die Grammatik Und so schön heißt es geht um die Dramatik von einer solchen Sprache Was ist korrekt gebildet und das ist nicht so wird gebildet ganz deutschen Bericht ist nicht um die Semantik kann sich die Semantik angucken stellen überhaupt gibt sich die Semantik Semantik wäre Bedeutung dass ich hier vor dass wir Bedeutung oder das das hier die Telefonnummer von Hans Müller oder was auch immer das wären Bedeutung Würdigung und sich bei der formalen Sprachen wieder bestehen größtenteils Grammatik das von Zeichenketten Natürlich dann auch nicht auf die üblichen Zeichen beschränkt ist sondern sagt aus irgendeinem endlichen Alphabet sollen diese Zeit stammen egal welches Vorbild das ist das chinesische oder an mathematischen sondern soll dazu sobald typischerweise wird das schon das muss man so auf der Tastatur Darum geht es um die möchte jetzt diese Sprache jeder einflussreichen üblichen Telefonnummern etwas Besser Formalisierung eine Möglichkeit dazu hatte ich die Vitus gezeigt Syntax Tiere am ich möchte dass so eine korrekte bildete übliche Telefonnummer mit 0 anfängt zu ziehen und so um zu sagen dass das was oder soll ich sagen ich möchte mit 0 anfangen
Und dann soll eine Zahl kommen Kein 0 ist kann nur 0 irgendwas keine Auslands Nummer also das jetzt eine Zahlen von 1 bis 9 eine Ziffer vor vielleicht sogar eine Ziffer von 1 bis 9 und danach können weitere Ziffern kommen und irgendwann kommt ein / /S r E: k S t r I C/ Und danach geht es auch noch irgendwie Walter dies mit den weiteren Ziffern wie kann ich das schreiben das jetzt auch beliebig viele sogar weitere Ziffern kommen so was wir damit eine beliebig viele weitere Ziffern wie kann ich das auch mal also die nächste so beliebig seien die 2. Ziffer soll 0 sein damit ich mit 0 0 starten zu ganz streng und auch alle formale
Metternich mit 0 0 Staaten die nächsten darf nicht nur seien aus dem Grunde und hier wirklich alle Ziffern erlauben von 0 bis 9 was kann ich tun veranstalten Damit es beliebig viele Ziffern von 0 bis 9 werden können das ist der Trick allenfalls / /S r E: k S t r I C/ Wissens und
Allenfalls und / /S r E: k S t r I C/ anschließend / /S r E: k S t r I C/ und einen Bogen um das heißt jetzt so eine gebildet die Telefonnummer fängt mit 0 an dann kommt was von 1 bis 9 dann kommt was von 0 bis 9 und dann kommt ein / /S r E: k S t r I C/ oder nach dem 0 bis 9 kommt noch was von 0 bis 9 und / /S r E: k S t r I C/ oder auch was von 0 bis 9 dann ein / /S r E: k S t r I C/ usw. Das heißt sie kann ich jetzt beliebig viele Ziffern von 0 bis 9 noch dazwischen kommt das kann auch weiterhin um schöner machen die nicht viel zu von von - ist wird auch nicht schön aber das wäre schon mal so 1. wichtigen den korrekte bildete Telefonnummer aussehen soll Nachdem / /S r E: k S t r I C/ soll sinnvollerweise nicht so weitergehen die 3 Ports Telefonnummer gewinnt auch die mit nun an das heißt die hab ich wieder was von 1 bis 9 Uhr aus Angst vor und danach kann ich wieder was von 0 bis 9 haben Wird in dieser 1. Annäherung beliebig 4 von der Sorte das heißt hier wirklich dann auch erlauben einerseits sich fertig und andererseits das sich dass sie auch wieder mehr haben kann nach den / /S r E: k S t r I C/ Einzelverfahren Uppsala fahren 1 bis 9 und nach der Ziffern von 1 bis 9 von 0 bis 9 ist Feierabend sind sehr kurze Telefonnummern oder noch vor von 0 bis 9 und noch eine von 0 bis 9 noch eine von nur besonders dann sowas Syntaxdiagrammen insofern dieser spezielle Form eines Syntaxdiagrammen als das ist wirklich komplett ausformuliertes wie später noch komplizierter Syntaxdiagrammen zeigen wo hier Platzhalter eingesetzt damit kann man das die komplizierte Ursachen von mir das ist die aller Art doch primitivste Form eines Syntaxdiagrammen ist komplett über den von belegt fertigen Symbolen aus meinem Vorbild billigt und nicht als Platzhalter Dass es eine Art diese Sprache zu beschreiben jetzt kann ich sagen welche Zeichenfolgen kostet von und / /S r E: k S t r I C/ anscheinend nur durch die Zeichenfolgen korrekt gebildet sind welche nicht zurückgebildet sind alle zurückgebildeten gehören zu dieser Sprache die durch diese Syntaxdiagrammen schrieben beschrieben wird allein gehören nicht dazu dass ist eine Art zu einer formalen Sprache zu beschreiben und der andere Arten nicht gleich auch tatsächlich dann und wofür zur für ein anderer dasselbe zu beschreiben sich wunderbar Ausdruck der der kommt tatsächlich beim Programmieren gerne mal vor insbesondere in der ganzen Internet-Technik
An da es das gegen Programmiersprachen sofort eingebaut dieses den regulärer Ausdruck weil es darum geht festzustellen ob ein bestimmtes der Zeichenfolge ein bestimmtes Format genügt verwendet man im Allgemeinen eine reguläre Ausdrücke ist eine Telefonnummer die jemand seinen Kunden Kontaktformular eingegeben hat wirklich eine Telefonnummer oder Städte und sind dann ist ein Interesse an der ist eine der 1. Adresse Stefan also die und Speckschicht / /S r E: k S t r I C/ steht das . die 2. all das kann man ja auch solche Art von Iran und sagen die einen Bereich der bei der die eine Welt in der es oder eine Telefonnummer aus die Sicherheit des zu tun ist nicht mit Syntaxdiagrammen das zu tun ist regulären Ausdrücken an
So sieht das so aus meinem um halten meine Telefonnummer soll mit einer 0 anfangen und jetzt hab ich eine Wahlmöglichkeit von 1 bis 9 und damit Klammern 1 oder 2 oder usw. bis 9 eine Wahlmöglichkeit irgendwas aus diesem Grund charmant und diese einzelnen Abteilungen mit - getrennt und dann kommt was von 0 bis 9 davon aber beliebig viel Definition Special sind von Sternchen und dass das einzige besondere was man braucht wie das Software gebautes ist wesentlich komplizierter man kann so was die Reform bis begann schreibt man kann sagen
Aber nicht man kann Bereich rausnehmen und kann sagen beliebig oft aber nicht 0 mal dass es überhaupt Problem wenn ich das so Schreiber als das beliebig oft einschließlich nun mal was nicht ganz korrekt ist für das muss mindestens einmal kommen sofern es sich das so schreiben einmal und danach beliebig oft einschließlich nun aber so sieht das Gerät aus dem muss ich einmal durch und danach kann ich es wieder von einem einmal und das Sternchen dann nun mal das einmal das zweimal das hintereinander das wird die Formulierung für den Fall vor dem / /S r E: k S t r I C/ stammt von der / /S r E: k S t r I C/ und geht es natürlich auch weiter auch ein zu formen
1 ist normal und danach mindestens einmal und dann beliebig oft einschließlich neuronale Netze Verfahren nur wissen ob was es gerne wissen Sie das mit regulären Ausdrücken aus dem sagte sondern dass das Sachverhalt geht mehr Möglichkeiten als nur den - unter Sternchen aber eigentlich die das ganze zurück auf den Strich der Sterne alles andere ist dann nur kommt vor dieser Sprache geschrieben durch diesen regulären Ausdruck das können wir mal in OpenOffice ankucken in OpenOffice kann nicht reguläre Ausdrücke direkt in dieser Form verwenden
Zugestimmt und aber war zu von vor die Telefonnummer sollen oder auch nicht Frage ist kann Maschinen einfach aus seiner Sprachbeschreibung herausfinden was eine korrekte werde die Telefonnummer ist und was kein gebildete Telefon es das finden Sie bei den Suchen und Ersetzen Funktionen aus 2 warum auch wichtig gebildet wird es uns zu Anfrage die 1. offensichtlich nicht richtig gebildet wegen des ABC ist da drin ist es nicht richtig gebildet weil das Frauen nicht mit nur 0 anfängt dieses nicht richtig gebildet weil / /S r E: k S t r I C/ steht vorne kann nur oder so machen das war ein Fehler drin ist nun der Städte / /S r E: k S t r I C/ und ist ok erstreckt sich der 2. Fall so vorsichtig unserer Arbeit suchen ersetzen ankucken
Sie können Suchen und Ersetzen der Option regulärer Ausdruck der können suchen und ersetzen sie fest Zeichenketten angeben sie sagen suchen wir alles 1 0 1 2 3 4 0 1 2 3 durch irgendwas in der Form aber sie können auch mit regulären Ausdrücken jetzt suchen wenn es darum geht also mehr Optionen der reguläre Ausdruck bis geguckt ob das was da gefunden hat Teil dieser Sprache aber das Wiedererkennen was jetzt passiert dass alle gebildeten Telefonnummern durch die Zeichenkette Treffer setzt der auszusuchen danach zu suchen einfach anderen aller gerettet werden sagte der Text großes üblichen Textverarbeitungsprogramm angewendet des Internet Programmierung verwendet man es dann irgendwelche Eingabefelder zu prüfen hat jemand seinen 1. Adresse plausibel eingegeben oder seine Postleitzahl seine Telefonnummer versehen angesehen wird weil Textverarbeitungsprogramm ist gern Suchen und Ersetzen die ich meinen Kramer ein also meine richtig gebildet die Telefonnummer soll Anfang mit einer nun und dann sollen die runden Klammern was kommen von 1 bis 9 und das kann man Geschichte schreiben Sie an wo man das Geschichte schreiben kann aber ich das ist das jetzt mal der grundlegenden Frauen so dass wir heißen mit runden Klammern 8 0 und 1 bis 9 und danach der bitte was von 0 bis 9 aber beliebig oft sind nach wie vor in einfach dass ich nicht sagen muss einmal mindestens so hat sich das Syntaxdiagrammen gebaut einmal mindestens was von 0 bis 9 geführt übersichtlich und danach beliebig oft einschließlich nun mal was von 0 bis 9 dann kommt ein / /S r E: k S t r I C/ dann kommt etwas von 1 bis 9 dann kommt wieder was von 0 bis 9 dann beliebig oft was von 0 bis 9 braucht glaube ich jedes Mal aus und die kriegen was sein steht es zu der Städte also Staats mit 0 dann eine zuvor von 1 bis 9 1 2 Wochen und dann eine zuvor von 0 bis 9 dann beliebig oft zuvor von 0 bis 9 und / /S r E: k S t r I C/ von als bisher und so weiter heftig und jedes Mal wenn er eine Zeichenfolge findet die diese musste möchte der Sprache ist für und Informatik sagen die formale Sprache ist dann soll das durch Treffer ersetzen nicht spannend zu an das auch ok macht man das jetzt 2 mit einem Tuch und Industrielohngruppen können was passiert ist so wie das 1. Treffer
Bis zum Abend ihren ist das Gerät gebildet bis brachte ganz dreist ok bis zu dem ABC das der 1. Treffer und ersetzt die Zeichen der bis zu dem aber man kann noch verlangen dass das wirklich damit einem Amtszeit Zahlen darauf bin ich ich froh wenn sie können diese Eingabe auch wirklich verlangen sie kurze kurz vor und besteht einzahlen um hoch und der Roman die Togo der dass froh dass wir noch abends wollte steht und in der Mitte einfach eine Brücke bildet die Telefonnummer und ersetzt zu zweit und sind verfolgt das ist kein Treffer die 2. 2. kann Treffer war nun an vor dem / /S r E: k S t r I C/ Zahlen und steht vor dem bis zu dem / /S r E: k S t r I C/ ist es Grid gebildet wird von einem welche Worte ist dahin ist somit gebildet das hier ist nicht durch den sie ist das Licht nach dem / /S r E: k S t r I C/ mit 0 an den ist wieder gebildet und ob es auch gut gebildet das sind reguläre Ausdrücke Aktion für solche Sachen benutzt zwar das Suchen und Ersetzen bei normalen Textverarbeitung und wurde das Internet Programmierung um festzustellen ob welcher Eingabe plausibel sind
Gut so sieht das Aktion aus ist aber so 2 Möglichkeiten dieselbe Sprache zu beschreiben man hier so Syntaxdiagrammen der primitiven Art und einmal so ein regulären Ausdruck entschlossen und sich als aber das kann man auch verfallen von bis oder oder alle aus zur und wir machen z. usw. gefügt dutzendweise Spezialzeichen üblichen Programmiersprachen und auch in OpenOffice und Konsorten in der Informatik beschränkt man sich hier auf das 2. und der Sterne das reicht für alles andere als eine ist nur Komfortfunktionen sozusagen und das mußte gelöst dass man das jetzt auch noch das 3. übersetzen kann in einem endlichen Automaten eine Einheit der Geschichte nicht automatisch das ist überraschend war Automaten denken wir aber Steuerungstechnik dann werden sie auf Automaten endlicher Automaten genau dieser Form auch massiv noch sehen der Veranstaltung schloss sich eine Maschine wird gerade mit halber Kraft Vollgraf Kraft gestoppt des gestoppt oder muss gewartet werden usw. ein Aufzug steht im 1. Stock im 2. Stock oder die Ampel steht auf Gelb usw. endliche Automaten gibt es bei den Maschinen extrem häufig besser beschäftigt man sich dann wieder Steuerungstechnik mit endlicher Automaten und in der Informatik findet man eine interessant Zusammenhang zwischen SPÖ solchen Sprachen und endlichen Automaten diese Prüfung auch so eine Zeichenkette geprägt ist der gebildet ist oder nicht kann man mit einem endlichen Automaten vornehmen und umgekehrt alle Zeichenketten die auf solche Art geprüft werden können kann man mit regulären Ausdrücken darstellen oder mit solchen ganz primitiven Syntaxdiagrammen das dieser einfachen hat aber wie soll das funktionieren sein endlicher Automat was war ganz abstrakt auf hat Zustände und dann in der theoretischen Format Single-Malt ist gibt andere Arten das aber nur und Standortdaten an etwas anderer das zu machen das ist steht die theoretisch Informatik normalen Zustände es gibt einen Startzustand wenig drücke oder die Maschine anschalte muss dieser Automat in einem ganz bestimmten Startzustand seien es gibt Übergänge zwischen diesen Zuständen die von irgendwelchen Ereignissen ausgelöst werden die man drückt auf einen Knopf wurde ist für die zum so viel Zeit bei war der Ampel zurück Übergänge wovon ausgelöst und dann gibt es sich mit diesen Sprachen beschäftigt auch zuständig werden zur doppelten Preis gemalt zusteht bis prüfen ob eine Zeichenkette Teil einer Sprache es funktioniert so ich führte über diesen Automaten mit der Zeichenketten dieses Schreiben durch die verschiedenen Zustände geht mit Hilfe der Zeichen einer Zeichenkette das 1. Zeichen einer ist wirklich von danach dagegen zum Beispiel wenn das 1. Zeichen ist für die von der Macht der ebenfalls das 1. Zeichen eines ist für die von danach dagegen nicht aus wenn und das kommt als nächstes ein aber dahin dahingehend wenn ich dahin gehend dass das sich sie nicht und so weiter also alle diese Falle schreiben Sie Buchstaben des Alphabets tragen und wird am Ende der Zeichenkette in einem Zustand sind dann sagen wir die Zeichenkette so Ende der Zeichenketten nicht in einem Zustand sind sollen die Zeichen der ist nicht so dass wir die Prüfung einer Zeichenkette durch einen endlichen Automaten
Also diese übergeben werden genommen werden jetzt als nächstes ein bestimmtes Zeichen kommt Und das Ziel des einen der Endzustände zu landen sagt man diese Automaten akzeptiert die Zeichenketten nicht am Ende der Zeichenketten einen der Endzustände ist sagt man der Automat akzeptiert die Zeichenketten nicht Das ist ziemlich abstraktes große Sommer für die Telefonnummer des provoziert und regulären Ausdruck sie ich muss irgendwo im Startzustand haben sowohl für ein Drama anders geht es nicht um was muss sich jetzt als nächstes machen ein endlichen Automaten einfallen mit der 0 dieser Zustand hat es nicht zu den anderen praktische bedeute diesen was ist die 1. Stelle auf jeden Fall wo ich einen Fall mit der 0 der sagt ok wenn alle 0 da man vergisst komme ich zu irgendeinem anderen Zustand und ich müsste es auch noch nicht bekannt streng sagen irgendwas anderes es komme ich zu einem Zustand in dem ich nach alles wieder bei sammeln kann schon mal ganz was nicht nur daran dass ist Startzustand 0 kommt man nicht da und da muss es weitergehen wenn da nicht nur kommt was anderes sagen was wir da
Und egal was da jetzt komme ich was wirklich ausdrücklich dran egal was jetzt kommt egal wann ich warte immer nur in diesem Zustand wenn es nicht mit 0 anfängt und nicht in der es nicht mit 0 anfängt nicht und rein und egal was jetzt kommt man nicht weiter in diesem Zustand auf jeden Fall wird das kein Zustand sein wenn es mit 0 anfängt damit das 2. kucken ok dann ist alles in Ordnung wenn jetzt was von 1 bis 9 kommt aus von 1 bis 9 Und wenn nicht 1 bis 9 kommt Dann kann ich wieder und in Maschinen und versumpfen ja in den Zustand Des 1. Komfort und einer Zeichenkette ich in den Zustand damit sich das ist Zeichen der Zeichenkette einen ist nicht 1 bis 9 ist sage möglich den Zustand von David hängen bleiben bis die Zeichenkette durch ist wenn es aber 1 bis 9 westlichen einen neuen Zustand und dann erwarte ich was von 0 bis 9 irgendeine zuvor von 0 bis 9 ist nicht nur bis 9 ist derselbe ist und es muss sich wieder zu meinem Fehler so wird mit Spannung jetzt möchte ich das über wiederholen können was heißt das nicht dass ich diesen Schritt jetzt wiederholen können
Dass es gibt noch einfach als dass die das machen müsse zu was haben wir das Sternchen für endliche Automaten und Situation so lustigerweise dieses hier dieser Zustand bleibt auf sich selbst stehen mir jetzt was von 0 bis 9 kommt und wenn nicht nur bis 9 kommt der geht es für beide Länder nicht von 0 bis 9 kommt nicht wieder in den Zustand der und dann so wenig da angekommen Bad sich das einmal 0 bis 9 kommt und den jetzt noch mal 0 bis 9 kommt schöne laufe einfach Kreise und jetzt wußte / /S r E: k S t r I C/ kommen
Sehen also nicht nur bis 9 ist sogar falsch was ich da jetzt schreibe ich muss ein bisschen anders arbeiten jetzt / /S r E: k S t r I C/ Kampf muss das ja auch erlaubt sein diesen Zustand muss erlaubt sein dass 0 bis 9 kommt oder de / /S r E: k S t r I C/ kommen / /S r E: k S t r I C/ Nachrichten ein 2. das heißt des ich Hauses in
Und zwar ist das der als / /S r E: k S t r I C/ nach 9 bis nach einem das Geld für diesen Fall den Zustand erwartet wird Ziffer Verfahren 0 bis ist nur ein oder den / /S r E: k S t r I C/ Braucht und nachdem / /S r E: k S t r I C/
So sollen als von 1 bis 9 kommen
Hier habe ich von 1 bis 9 In einen neuen Zustand und Chef der was anderes kommt als 1 bis 9 nicht wieder zum meinem vielleicht nicht ganz so neuen nicht und war gerade gucken wir nicht auch wenn das Vorhaben eine Zahl von 0 bis 9 und beliebig häufig eine Zahl von 0 bis 9 Tausend geht es weiter mit einer Zahl von 0 bis 9 mindestens aber noch mal eine Zahl von 0 bis 9 überlegen ob ich die hier schon als machen kann man zusammen überlegen ist das das ist das dieselbe Sprache wenn ich das alle ist das dieselbe Sprache wie ich sie oben hat dass ich hier Aufführung mit einem Zustand der dann wird durch Eingabe von 0 bis 9 immer wieder sich über 4 geführt wird und das dann Zustand ist wie das dieselbe Sprache die ich hier oben geschrieben habe hier wirklich nach / /S r E: k S t r I C/ als zuvor von 1 bis 9 dann eine Ziffer von 0 bis 9 und dann kamen oder einem oder viele nochmal Ziffern von 0 bis 9 was ist aber schon Frage dass es lustigerweise nicht diese Sprache hier was ist der Unterschied zu meinem Manne Sprachen von Zustand darf wiederholt werden dürfte es darf auch nach dem Zustand wieder andere Zustände zurück wichtig ist nur wenn die Zeichenkette durchgelaufen ist das dann die Maschine diesen Zustand steht die Zeichenkette laut ist genau dann wenn überhaupt was mir jetzt fehlt ist das nach der 1 bis 9 mindestens einmal noch 0 bis 9 kommen muss so wie ich das Syntaxdiagrammen aufgeschrieben habe hier muss mindestens einmal 0 bis 9 , klarmachen dass dieser Versuch auf mindestens einmal muss 0 bis 9 kommen
Das passiert hier nicht 1 ist noch ein wenig in den Endzustand Zeit und sind daher auch für den Zustand der akzeptiert
Ich hätte nicht aber zwangsläufig eine weitere Ziffer von 0 bis 9 das auch noch einen weiteren Zustand das kann sich der Zustand seien auf einen weiteren Zustand Ziffern von 0 bis 9 mit einem weiteren Zustand das ist der Zustand und der liegt in der Schleife wenn ich nach dieser Ziffern von 0 bis 9 noch weitere zu habe von 0 bis 9 eine Aktion bleibe ich in diesem Zustand und gucken 1 bis 100 Meter auswendig nicht 0 bis 9 habe es wieder zu diesen Fehler gehen und wenn ich hier nicht nur müssen 9 aber es ebenfalls zu den
Brauche In der Informatik kann man dann einen Tag vor verwenden zu beweisen dass die Sprachen man so beschreiben kann genau dieselben sind die man so schreiben kann mit regulären Ausdrücken denen sich die regulären Sprachen ist nicht so wichtig an dieser Stelle nicht wollte die vorführen was für Arten es gibt Sprachen zu beschreiben also eine übliche Arzt da ist praktisch auszudrücken sind reguläre Ausdrücke insbesondere dass viele Programmiersprachen eingebaut ist und eine ganz andere Auffassung in der theoretischen Format entwickelt sind diese endlichen Automaten
Ich prüfe eine Zeichenkette zu einer Maschine Maschine ist keine Ampel und keine Druckerpresse und keinen Aufzug sondern eine Maschine die Zeichenketten warum nicht und und der Gedanke ist die Zeichenkette Muster zu sorgen dass diese Maschine durch ihre Zustände läuft jedes Zeichen der Zeichenkette quasi eine Eingabe drückte den auch nur drückte den auf 5 drücke den Knopf 0 und so weiter Zeichen ist eine Eingabe und ich frage mich zum Schluss steht diese Maschinen einen der Zustände die ich als Endzustände markiert habe ich aber ist die Zeichenkette korrekt wenn ein Zeichenketten nicht doch das wir jetzt ein Automat der meine etwas Komisches Sprache der rückgebildeten Telefonnummern prüft
Und die ist die gab es ja so ungefähr auch schon mal als Singer Aufgaben was ist kompliziert erklärt ist die Anzahl fest ich bin ich jetzt nicht bis dahin durchführen lernest programmieren sich sehr zu Fuß gelöst dann Seat hab man das sondern es der 14. durchgegangen prüfen kann man kann sobald man auf diese Abstraktion wir es mit regulären Ausdrücken und endlichen Automaten kann alles sehr systematisch an CC ich diesen endlichen Automaten einfach Programmierer und damit prüfen ab irgendwelche Zeichenketten Telefonnummern in diesem speziellen Formats es geht es nicht nur durch wenn sie einmal es der kam auf aufgemalt haben haben nicht mal einfach die zuständige durch Nummer 1 in die Zustände als solche sind nicht so richtig sind vor der naja gut das hat was mit dazu tun ihr Zustand dass mit akzeptiert zu tun an das ist der letzte vor dem / /S r E: k S t r I C/ des 1. vor dem / /S r E: k S t r I C/ mit etwas Mühe kann man die schon Bedeutungen geben aber eigentlich muss gar nicht überlegen was die Bedeutung dieser Zustände und ich hab jetzt einfach die Übergänge Ereignisse und das Ganze baulichen einer Tabelle zusammen und diese Tabelle oder also nicht nur die allgemeine Durchsage das Zustand 0 1 2 3 und Prozent
3 würden
Es haben
York das sind also 8 Zustände insgesamt die schwarze solch einfach eine Tabelle
Und in der Tabelle steht da was wie sich diese Zustände weiterentwickeln sollen wenn bestimmte Eingaben kommen sehen was wir haben können ich muss gucken ob die Eingabe 0 ist ich muss gucken ob sie 1 bis 9 ist ich muss gucken ob sie / /S r E: k S t r I C/ ist oder alles andere eigentlich hab ich effektiv nur 3 Eingaben ist die Eingabe 0 ist die Eingabe eines zuvor von 1 bis 9 oder ist die Ziffer / /S r E: k S t r I C/ oder alles andere
Nicht wirklich als ebenso natürlich 4 also die 4 Fälle Venedig bei den Eingabe unterscheiden muss und ich dann einfach C eine Tabelle die das Ganze Verarztet setzt sich dann so aussehen aber letztes Jahr hat die anders von Bezeichnern ganzen Tabelle andersrum aufbauen haben und die jetzt vor stets die Tabelle aufzubauen ist vor ist das hier in der Spalte Indiens die Eingabe steht also nur 1 ist noch ein / /S r E: k S t r I C/ und alles andere Und das Auf der stark der Arbeit Santa Achse zuständig die entfernen oder wie es weiter der und dann schreibe ich auf diese Kreuzungspunkte folgendes wenig Zustand 2 werden und das kann erst ein Ghana 1 bis 9 schreibe ich hier was passieren soll Auf die die jeweilige Ports wenig Zustand 2 und das Band 1 bis 9 habe ich daran dass der nächste Zustand sein sollen gucken wenig Zustand 2 einen Zustand 2 wegen des kam es 1 bis 9 Teilmenge davon nicht Zustand 3 als eine
Tabelle aus und speist das dann in sein Programm sein das Programm ackert einfach durch die Tabelle durch ist weiß Ich bin Zustand so und so viele jetzt kommt die Eingabe so und so also muss sich dann im Zustand so so unzufrieden und als ob das Programm ob es einen der Endzustände ist in diesem Fall nur Zustand 6 ist in der Tat und wird auch das also wenn die nur kommt doch jedem Zustand und wird 3 als ich habe die auseinandergehalten die 0 und die 1 bis 9 um möglichst wenig Ereignisse zu haben statt eigentlich nur 4 Eingaben sind hier sage ich eigentlich immer eigentlich habe ich dann 2 Eingabe des Schiedsrichters zumal ich damit ein nicht Eingabe 8 Smalltalk oder die Eingabe 0 so würde das anstrengt aufgemalt
Der Einfachheit halber wird sich also von 0 bis 9 jetzt 2 Ereignisse die von 2 zu 3 für das Ereignis nun gut sollte als das 1 bis 9 So oder 1. Job ist jetzt diese Tabelle C zugießen Zustände aber schon ganz freies durchnummeriert von 0 bis 7 Diese Eingaben könnte man jetzt mit einer und machen das sie wirklich was Land das haben sie ohne und schon mal Slash oder so was ich für dich jetzt auch einfach mal um das ganz schlicht zu haben
Durch den variieren 0 1 2 3 insgesamt ein zweidimensionales und diesen zweidimensionalen stehen einfach Zahlen welcher Zustand wird als nächster angenommen
Sogar als scharf vielleicht viele Anzahl stark ein zweidimensionales es ist 8 bald schon und 4 hoch die was das so müssen sie nicht eingeben und die 4 reinschreiben das kann aber selbst
Und das sie nicht ganz im Netz Zu jeder Zahl 8 Sachen stehen 8 davon 4 Stück vor
Es da so haben netterweise schon
Der Hamas Spalten mit der Nummer 2 muss das losgehen mit 3 3 vielleicht machen wir die nachts ändern Zustand 2 / /S r E: k S t r I C/ ganz Zustand zwar / /S r E: k S t r I C/ der und 7 Grad Zustand 2 was anderes kommt zu 7 also dass das alles 7 7 seinen 1. eintragen 3 3 7 7 in der Spalte Nummer 2 sich bald zwar Nummer 1 7 und das geht noch ein Ding das man sofort komplett eintragen kann
Wenig Zustand 7 einmal gelandet dann soll ich nie wieder rauskommen aus egal was passiert egal welcher Eingabe kommt Zustand 7 ich muss wieder Zustand 7 genannt was heißt das für diese Tabelle wenig Zustands bilden und dann kommt 0 solchen Zustands bleiben wenn ich Zustands bin das kommt als bis 9 so und so weiter hinten soll es immer auf der sich bleiben warum noch beschenkt muss über die heißen die Gruppe bestätigte ca. 1 2 3 4 5 6 7 8 1 zu 1 zu 4
Zur Bestimmung von 4 6 8 ja so wie geht 2. wenig Zustand 0 dann kann es nur mit 0 weiter weitergehen das ist das 1. mögliche die 1. mögliche Eingabe der 1. Zeile nur oben steht bei der 0 die 1 ansonsten steht über die 7
Steht die 1 und ansonsten steht als 7 Bei der 1 geht es nur mit der 1 bis 9 weiter und ansonsten immer zum Zustand 7 1 bis 9 war die 2. Zeile gibt es also beim Zustand eines von der 2. Zeile was und ansonsten muss sich immer wieder 7 2 2 besteht bei der einst die 2. ansonsten die 7 sich nicht an das war und ansonsten die Zustand Nummer 2 und 2 Arten wird kommt der Zustand oder ich Zustand Nummer 3 der Switch will bei der 0 und bei der 1 bis 9 das bei mir die 2 verschiedene Eingaben werden nur weil der 1 bis 9 geht es wieder da war beim / /S r E: k S t r I C/ Lizenz 4 und ansonsten gibt es 7 also Zustand selbst zurück zu 0 ist 10 Zustand selbst zurück 1. 1 bis 9 bis 10 Zustand zurück wenn es ein / /S r E: k S t r I C/ war gibt ist und wenn es alles andere geht Zustand das waren 0 1 2 3 der Zustand und alles zu schaffen auf 4 ist nach 1 bis 9 ist das war der 2. erledigt zur 500 sonst nicht immer zufrieden
Ist das neue ist hier ich nicht zu 5 ansonsten wird es von der Zustand auf 5 kann also 0 erlauben und die 1 bis 9 ist sind die 1. beiden Zahlen 1. Band sein steht eine 6 und ansonsten steht die 7 besteht eine 6 und stellt sich
Und der Zustand mit der Nummer 6 der hier bei der 0 steht für die selbst 1 bis 9 steht die 6. das schon und - die sie selbst erstellt selbst erstellt diesen darstellt die 7 das ist die Tabelle gesehen wird jetzt auf diese Art also ein Diagramm nicht mal so ein Diagramm des umgewandelt in eine Tabelle der Nutzer einstimmig Schreiber einfach wieder auf welche Weise womit verbunden ist die Tabelle und mein Programm verarbeitet wird diese Tabelle was überhaupt nichts von Telefonnummern und was auch immer ist sie nur diese Tabelle was jetzt in der Tabelle oben und sich auf den Markt zu haben ist das ausprobieren kann also Zeichenkette genauer gesagt es ist ist eine Zeichenkette
Das ausprobieren kann dafür sorgt dass ganz überhaupt natürlich hübsch welche Funktionen verpackt sein und eigene sie derzeit keine Dateien verpackt sein das es jetzt auch ist das schön gelöst was was die Programmierpraxis davon sie angeht richteten sich jetzt wirklich nur die man damit umgehen kann ich mir das 8 sogar macht also sich die Männer Zeichenkette war ein so jetzt möcht diese Zeichenkette prüfen das heißt es muss diese Zeichenkette Buchstabe für Buchstabe ablaufen und der Automaten mir weiterschreiben
Was muss ich jetzt tun kann der 2. Als und durch diese Zeichen jetzt durchzugehen ich will ein Zeichen nach dem anderen einführte an den Automaten nicht von aber seine for-Schleife ich weiß wie viele Zeichen des sind es geht schönen einer Schritten das komische dass der irgendwo muss jeden Vorschlag verstehe ich war da natürlich auch auch für die ganze Zeit nahm
So sollte diese 2. gelte oder am versehen als die maximal die meine 12. 4. aber ständig zu haben und jetzt aber wird
2
Wird in einer Schritt Obst einem Schritt und in der Schleife billig jetzt Zeichen ich den Automaten führt
An
Ich muss man erkennen wo ich gerade Automaten welcher Zustand gerade angesagt ist
Und dann komme ich in der Tabelle nachzubilden zuständig die gehen muss die merklich mir welcher Zustand gerade angesagt ist um sich zu merken wo sie gerade sind in dem Gestrüpp welcher der Zustände gerade angesagt ist es zu merken was ist die Nummer des Zustands Zustände jetzt benannt werden mit einer um und den Start und Ende und Fehler und vor dem / /S r E: k S t r I C/ nachdem / /S r E: k S t r I C/ dann
Wird ein und aus die der waren aber ich hab ich aber durchnummeriert nehmen oder analog zu der Tabelle die derartige gesagt an seinen Charme von Zustand zum anderen stehen sagen das Anzeigen scharf die Nummer des Zustands der nicht gerade mit selbst und der Anfangszustand sinnvollerweise wartet auf der mit der Nummer 0 ist das auf die Nummern von ob was passiert setzt enthalten in welchem Zustand ich gerade bin ich gucke mir das nächste Zeichen an Google in der Tabelle nach welchen Zustand jetzt muss ok was war das nächste Zahl ist der relativ einfach erst mal aus dieser Zeichenkette das Zeichen an der Stelle kommen Sie da kann auch aus aber ergeben kann man auch die Zeichenkette ist aus diesem gibt das soundsovielte Zeichen raus und jetzt will ich feststellen ob dieses Ding kann nun ist oder eine 1 bis 9 oder ein / /S r E: k S t r I C/ ist wird irgendwas anderes das sondern nach dann die Nummer 4 der z. sagen willst würdest richtig in der Zeile mit der Nummer 0 nachgucken 1 1 bis 9 ist mächtig sein mit der Nummer 1 nachgucken ganzen / /S r E: k S t r I C/ ist mit der Nummer 2 und wenn das alles andere ist derzeit nur 3 das muss jetzt übersetzt nicht bauen wir eine Variable also nicht für wegen ein verbilligen oder so was
Verstanden Initialisierung das klar zu machen also so für ein aktuelles Zeichen dass da gerade angesagt ist die Ziffern und ist so muss es ja aus der das Zeichen war von identisch mit der Ziffern 0 nicht die die einfach Vorzeichen vergessen es ist ja nicht wohl Nummer gleich 0 sondern diese Symbol Nummer ist die diese Nummer des Bots 0 das der Fall ist dann habe ich das Ereignis mit der Nummer 0 die Eingabe der
8 Fuß die Sportler und auf diese Maschine werden und aber als das Problem der werden sonst werden das nicht nur lösten jetzt muss ich Glossar 1 bis 9 s 1 bis 9 ist
Dann merke ich mir die Nummer eines Ereignisses ist 1 wie sie das ausformuliert wird jetzt prüfen ob das Zeichen was mir eine Ziffern von 1 bis 9 ist in der Tat das ist nicht zwischen diesen beiden Codes einschließlich ist größer gleich Zeichen gut für die 1 Prozent für 1 und es ist kleinergleich dem Zeichen gut für den 9 habe ich eine Ziffer zwischen einer gleich eine sehr zwischen 1 und 9 so und das ist das Ereignis mit der Nummer 1 und wenn das
Es wollte sich alle ausschließen gegenseitig könnte das es auch weglassen müssen schon aus dem lässt man sich klar die sich durch die die sie sich alle gegenseitig aus es würde wenn sie brauchen bisschen schneller aber wesentlich Effekt ist dass sie alle Leute die dieses Programm lesen mitteilen dass sie sich bewusst dass diese Fälle sich gegenseitig ausschließen so wenn es ein / /S r E: k S t r I C/ ist dann merklich mir eine 2 und ansonsten ist es alles andere und ich merke mir eine 3
So könnte man das aufschreiben dass es jetzt das Übersetzen von diesen Eingabemöglichkeiten 0 1 bis 9 / /S r E: k S t r I C/ alles andere in eine Zahl 0 1 2 3 kann es auch etwas eleganterer machen statt des hinten nach dass der Bauern können Sie erfahren auch sofort sagen wenn erst mal an es ist alles andere gleich 3 und prüfen nur noch die 0 1 bis 9 / /S r E: k S t r I C/ ich es jetzt so auf ein übersichtlicher weil heißt das sich alles nicht habe und jetzt kann ich in einer Tabelle nachgucken meine Tabelle sagt mir dass der am 1. Kardinal die hier mir nehmen die Nummer des Ereignisses das ist dass die 2. Koordinaten den aktuellen Zustand und was rauskommt ist der nächste Zustand was schreiben sie von jetzt auf zuschreiten diesen Automaten die muss jetzt ja auch in der Tabelle nach geguckt werden die hieß es da keine an sehr schön kann so soll das heißen eines Menschen sei Tabelle heißen dieser Tabelle guck ich nach der 1. ist die Zahl der das ist das Ereignis das wir gerade ausgekuppelt haben es erwischt die von fest steht der alte Zustand
Zustand 0 1. Spalte Zustand eines 2. Spalte usw. sogar das zu verstehen was mache ich jetzt mit diesem Ergebnis was mache ich mir das sich aus der Tabelle ausgelesen habe genau das ist der neue Zustand weisen das einfach Z Zuses bezieht heraus das ist der endlicher Automat wenn sie einmal als Tabelle formuliert haben
Ich habe gerade aus der Zeichenkette normalen welcher zeitlich ich bin ist die Zahl 0 gekommen ist die Zahl 1 bis 9 bekommen Ziffer 1 bis 9 bekommen das ein schlechtes kommt ist was anderes bekomme ich weiß welcher Spalte ich bin dass der aktuellen Zustand jetzt auf der Kreuzung nach weiß dass der nächste Zustand
Was ist dann einfach zeitgleich Sowie ich jetzt heraus fertig sind ob der diese Zeichenkette dicht am Anfang gegeben habe ob diese Zeichenkette jetzt auch wirklich diesem Format hat was muss sich jetzt machen
Genau das ist der Trick der fertig sind mit der Zeichenkette über die abgearbeitet haben gucke ich einfach ob ich zum Zustand Nummer 6 der einzige Zustand q ob ich irgendeinen der Zustände sind aber eine nur sehr wenig da gelandet war Geld ok wenn nicht weil sie nicht ob und wann sie ihr sportliches einfach mal 6
Gebe ich einfach aus ab Und ansonsten gebe ich aus dass es nicht wahr
Dazu brauche ich jetzt für das bringt noch von der Union
Sohnes zur Fehlersuche gespannt wie der jetzt genau damit den 1. und das ist ja aber was ich geschrieben habe das ist aber nichts was sich da geschrieben haben so dass es finster
Für die eckigen Klammern hinter das hinter dem Variablennamen aber gucken was war damals als wir noch einen Fehler immer noch Politik zu lang das heißt es sollte man einen Chip einstellen der bisschen mehr Speicherplatz als und General auch 30 x gucken ob es gespeichert
Ok der kann das Wissen das heißt grammatisches jetzt ok das ist genau das was man auch gesagt haben zu formalen Sprachen der Compiler findet das ok das ist also grammatische ok ob es das jetzt tun was ich will ist ganz andere Sache des semantisch richtig ist 19 das nicht nur laufen und auch nicht ist es wichtig dass wir 2 wo auch ok zu dieser Telefonnummer sagte mir korrekt spannend sich 2. / /S r E: k S t r I C/ Bauer nicht korrekt es müsse 900 verschiedene Fälle mal durch was ist wenn ich mich mit 0 State
Das kann natürlich hübsch automatisieren es gibt dann einfach Übeltäter mit denen man genau was automatisieren kann Unit Tests sie schreiben 100 oder tausend des Verlauf und das jeweils auskommen sollen und und die die automatisch nur was nicht direkt auf
Als 2 Sachen eingebunden aber ich unten wird benutzt habe zur Ausgabe Standard 1 2 3 4 die Länge der Zeichenkette benutzt hat man es nicht sie testen einfach einfach sein eingehen ist ja nicht sogar der diesjährige sah das zu testen und ist ist wirklich sauber durchtesten haben alle möglichen Kombinationen mal ausprobieren so sieht das Programm aus und sie sehen dass das im Unterschied zu der Seminar Aufgabe was hatten Telefonnummern erkennen ob sie das richtige Format haben dann der sind diese Seminar nach Aufgabe ist das einfach anderer Art anzugehen total formalistisch ich schreibe eine Sprache Abstraktion was ist diese Sprache der korrekten Telefonnummern übersetzt das in einen Automaten ersetzt den Automaten eine Tabelle sie dass sie jetzt passiert dafür einfach nur nach diese Tat durch das ist alles sehr viel mehr als das was wir haben das ist wesentlich leichter zu beherrschen beim Programmieren als wenn man habe sich über nicht aus jetzt muss dieses Zeichen kommen und dann muss es Zeit kommt an das ist viel leichter zu verstehen vielleicht dazu für ihren auch kann sich vielleicht überzeugen dass das Richtige tut seines verkraften zu so einer Lösung und das hübsche dass sich hier von mit OpenOffice gezeigt dass es in dieser Form mit regulären Ausdrücken ist es sowieso meisten Programmiersprachen eingebaut für sie gibt benötigen Sie der zu laden können die dann auch so was verstehen dann ist es gar nicht selbst programmieren schreiben nur abstrakt wie die Sprache funktioniert die Sie da haben vor
Abschließen nochmals deutlich zeigen dass die sprachen von dieser Art in denen sich die regulären Sprachen sprachen sie mit regulären Ausdrücken schreiben können und endlichen Automaten testen können diese Sprachen ist ist nicht gerade sehr aussagekräftig sie nicht alle sehr vielseitig was man zum Beispiel nicht prüfen kann mit solchen Sprachen ist auch Klammern auch wieder zu gemacht werden wenn es beliebig viele Klammern sein dürfen wenn sie eine Sprache bauen wollen in der sonst ausgeklammert werden kann und dann war sie dafür sorgen dass auch immer genau so auf die Klammern wieder zu gibt das ein Problem mit diesen regulären Sprachen nicht erlauben wir dass es hier beliebig viele endlich aber beliebig viele Klammern sein dürfen kann ich das nicht mit einen endlichen Automaten prüfen ärgerlicherweise also das ist ein ganz dicke Limitierung dieser Chef Sprachen die man so darstellen kann mit und deren Auswirkungen und mit endlichen Automaten der prüfen kann was gerade noch mal überlegen warum kann man das nicht zu ein Automaten was aus der nicht nicht sicherstellen will dass diese Sprache vorne Tausend man auf hat auch genau Tausend Klammern wieder zu oder wenn sie von einem jungen Mann auf dann auch in auch wieder eine Million Klammern zu halten was ist das Problem wenn sie einen einzigen endlichen Automaten hinmalen der das prüfen können soll aber genauso viele Klammern wieder zu wiederzugeben die vorher aufgegangen sind
Haben sofort schon praktische Lösung für das Problem die Zähne einfach die Klammern mit hier aufwärts und der abwärts das dumme ist das endliche Automaten nichts kann hat ja nur endlich viele Zustände der kann deshalb nicht beliebig hoch das Problem ist folgendes mit so Automat ist wirklich dumm dass man daran der kann nicht beliebig Netz der muss innerhalb des 1. Klammer hat einen Zustand sein die 2. Klammer das nachher auch wieder zurück feststellen kann ob den 2 oder eine Clamart 3. Klammer da kommt es noch einen anderen Zustand sei in die vierte Klammer kommt muss noch einen Zustand sei um nachher wieder feststellen zu können das sind 4 Klammern so nötig sind und nicht weit Klammern nötig sind das heißt wenn sie verlangen das ist hier eine Million Klammern of annimmt und abzählt dass es auch wieder eine Million Klammern zugeht brauchen sie mindestens eine Million Zustände sie verlangen dass die Zahl der Klammern beliebig sein darf endlich aber beliebig sein darf wird das nicht funktionieren ist nicht unendlich groß ist kann kein endlicher Automat das Profil es gibt eine billige Lösung sieht es einfach Klammern ordentlich Automat kann das nicht unter der endlicher Automat das nicht ganz geht es dann auch hier mit den regulären Ausdrücken absurderweise nicht
Es gibt eine allgemeine des Arguments des kommt in der theoretischen Informatik dann vor sich was Frist an das Pumping-Lemma das Pumping-Lemma für reguläre Sprachen ist jetzt der oder die sich studieren Raketentechnik an Sprachen also versprachen dieser Art
Wenn ich so einen Automaten habe Und ich jeder mit einem sehr sehr lange Wortreihen oder uns mit einer sehr langen Telefonnummer Jeder war dieser Automat läuft durch die Gegend was muss ich irgendwann passieren wenn das Wort sehr lange es mit dem ich die
Nicht noch mal auf wenn sie sich vorstellen dass sie automatisch Zustände sowas hat schon oder eine Milliarde eine feste endlich Zahl von Zuständen hat und sie mit einem super super super lagen in superlangen Wort eine superlangen Zeichenkette daran diesen endlichen Automaten irgendwann muss was passieren irgendwann irgendwann muss dann eine Schleife kommen das ist der irgendwann muss sich das Ding wiederholen irgendwo Mustern Schleifen sein wenn sie mit einer Million Zeichen reingehen dieses Karten Tausend zustimmen muss sich von Schleife ergeben werden denn diese Zeichen der die mit einer Million Zeichen erlaubt ist also wenn sie so eine lange Zeichenkette erlauben tatsächlich der Sprache muss in diesem Automaten eine Schleife drin sein und das hat sofort eine Folge der eine Schleife drinnen heißt das sich ganze Schleife einmal durchlaufen zweimal durchlaufen tausendmal durchlaufen zehntausendmal durchlaufen auch all das muss erlaubt sein das ist dieses sogenannte Pumping-Lemma für reguläre Sprachen es gibt auch noch ein anderes für andere Sprachen
Wenn diese Sprache ein Wort das Land genug ist dann können Sie dieses Wort in 3 Teile und dieser Teil der mit den können Sie nicht wiederholen weil das einfache Schleife sein muss sie müssen mindestens eine Schleife drinnen haben Teil dieses Wort für Zeichenketten den der Schleife läuft können Sie beliebig oft wiederholen und auch das muss wieder erlaubt sein also wenn das ABC ist das ein lautes Wort ist dann muss auch dieses hier am C ein erlaubt das Wort sein oder einfach die Schweiz und das muss aber und jetzt einmal erlaubt Wort sein das geht muss dass das Geld usw. dieser Teil der Schleife muss beliebig oft wieder Huber auch wieder erlaubt sein das ist eine Eigenschaft von diesen reguläre Sprachen hier und das schließt ganz viele Sprachen sofort raus weil nicht einfach in jeder Sprache so einem bestand darauf verzichten und werden daher die sich vor reguläre Sprachen haben sofort die Eigenschaft sie sehr lange wird drin haben gibt es daran teil die beliebig wiederholt werden was sich am und . hier das erlaubte Wort Bestandteile auf
Sortierverfahren
Datei
Zustandsmaschine
Formale Sprache
Uniforme Struktur
Keller <Informatik>
Endlicher Automat
Warteschlange
Datenstruktur
Informatik
Computeranimation
Theoretische Informatik
Formalisierung
Formale Sprache
Web-Seite
Informatik
Zahl
Quick-Sort
Computeranimation
Zeichenkette
Ziffer
Zahl
Computeranimation
Programmierer
Ziffer
Variable
Formale Sprache
ART-Netz
Computeranimation
Aggregatzustand
Programmiersprache
Regulärer Ausdruck
Netzadresse
Computeranimation
Software
Abteilung <Mathematik>
Computeranimation
OpenOffice.org
Regulärer Ausdruck
Strich <Typographie>
Computeranimation
Neuronales Netz
OpenOffice.org
Computeranimation
Funktion <Mathematik>
Mathematische Größe
OpenOffice.org
Datenbank
Internet
Datei
Formale Sprache
Regulärer Ausdruck
Programmierung
Netzadresse
Computeranimation
Netscape
Regulärer Ausdruck
Informatik
Zeichenkette
Aggregatzustand
OpenOffice.org
Internet
Firefox <Programm>
Datei
YouTube
Aktion <Informatik>
Regulärer Ausdruck
Programmierung
Zahl
Computeranimation
Regulärer Ausdruck
Editor
OpenOffice.org Calc
Client
Wort <Informatik>
Textverarbeitung
Internet
OpenOffice.org
Programmiersprache
Zusammenhang <Mathematik>
Datei
Aktion <Informatik>
Zustandsmaschine
Kraft
Automat <Automatentheorie>
Zeichenvorrat
Endlicher Automat
Ereignisgesteuerte Programmierung
Computeranimation
Regulärer Ausdruck
OpenOffice.org
Zustand
Normalvektor
Informatik
ART-Netz
Zeichenkette
Computeranimation
Regulärer Ausdruck
Zustandsmaschine
Automat <Automatentheorie>
Computeranimation
Zeichenkette
Computeranimation
Zeichenkette
Zustandsmaschine
Hausdorff-Raum
Computeranimation
Ziffer
Zahl
Computeranimation
Zeichenkette
Computeranimation
Computeranimation
Regulärer Ausdruck
Programmiersprache
Ziffer
Zustandsmaschine
Aktion <Informatik>
Meter
Reguläre Sprache
Informatik
ART-Netz
Computeranimation
Automat <Automatentheorie>
Zustand
Computeranimation
Zeichenkette
Regulärer Ausdruck
Programmierer
Zustandsmaschine
Tabelle
Zustand
Computeranimation
Zeichenkette
Computeranimation
Teilmenge
Ziffer
Tabelle
Zustand
Formation <Mathematik>
Computeranimation
Tabelle
Computeranimation
Tabelle
Zustand
Zahl
Computeranimation
Update
Information
Zahl
Computeranimation
Tabelle
GRADE
Update
Zustand
Information
Computeranimation
Update
Information
Computeranimation
World Wide Web
Update
Switch <Kommunikationstechnik>
ART-Netz
Computeranimation
Update
Formation <Mathematik>
Computeranimation
Schar <Mathematik>
Datei
Diagramm
Tabelle
Automat <Automatentheorie>
Update
Information
Computeranimation
Funktion <Mathematik>
Zeichenkette
Schar <Mathematik>
Automat <Automatentheorie>
Update
Information
Computeranimation
Update
Information
Computeranimation
Schar <Mathematik>
Variable
Google
Tabelle
Automat <Automatentheorie>
Update
Zustand
Information
Zahl
Computeranimation
Zeichenkette
Update
Information
Computeranimation
Ziffer
Vorzeichen <Mathematik>
Initialisierung
Update
Information
Computeranimation
Roboter
Ziffer
Update
Decodierung
Information
Ereignisgesteuerte Programmierung
Computeranimation
Soundverarbeitung
Übersetzer <Informatik>
Tabelle
Automat <Automatentheorie>
Update
Information
Ereignisgesteuerte Programmierung
Zahl
Koordinaten
Computeranimation
Schar <Mathematik>
Update
Information
Computeranimation
World Wide Web
Tabelle
Angewandte Physik
Update
Endlicher Automat
Information
Computeranimation
SIZ
Ziffer
Update
Zustand
Information
Zahl
Computeranimation
Zeichenkette
Schar <Mathematik>
Update
Ovoid
Information
Computeranimation
Schar <Mathematik>
Fehlermeldung
Microsoft Network
Position
Compiler
make
Formale Sprache
Konfigurationsraum
Datenmodell
IMS
ACCESS <Programm>
Debugging
Assembler
Information
Computeranimation
Open Source
Quellcode
Downloading
Update
Ovoid
Datenfluss
Compiler
Hardware
Schar <Mathematik>
Softwaretest
Konfigurationsraum
Browser
Datenendgerät
Information
Computeranimation
Keller <Informatik>
MEGA
Interrupt <Informatik>
Code
Downloading
Ein-Ausgabe
Update
Disassembler
FOL
Ovoid
Display
World Wide Web
Programmiersprache
Schar <Mathematik>
Programmierer
Länge
Tabelle
Automat <Automatentheorie>
Information
Computeranimation
OpenOffice.org
Regulärer Ausdruck
ENUM
Zeichenkette
World Wide Web
Regulärer Ausdruck
Abschließung
Task
Limitierungsverfahren
Zustandsmaschine
Automat <Automatentheorie>
Reguläre Sprache
Information
Computeranimation
Computeranimation
Regulärer Ausdruck
Zustandsmaschine
Automat <Automatentheorie>
Zustand
Endlicher Automat
Zahl
Computeranimation
Parametersystem
Automat <Automatentheorie>
Reguläre Sprache
Computeranimation
Theoretische Informatik
Zustandsmaschine
Automat <Automatentheorie>
Zustand
Reguläre Sprache
Zahl
Computeranimation
Chipkarte
Zeichenkette
Reguläre Sprache
Computeranimation
Zeichenkette
Computeranimation

Metadaten

Formale Metadaten

Titel 13A.1 Formale Sprachen, reguläre Ausdrücke, endliche Automaten, Pumping-Lemma
Serientitel Informatik 1, Winter 2011/2012
Autor Loviscach, Jörn
Lizenz CC-Namensnennung - keine kommerzielle Nutzung - Weitergabe unter gleichen Bedingungen 3.0 Deutschland:
Sie dürfen das Werk bzw. den Inhalt zu jedem legalen und nicht-kommerziellen Zweck nutzen, verändern und in unveränderter oder veränderter Form vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen und das Werk bzw. diesen Inhalt auch in veränderter Form nur unter den Bedingungen dieser Lizenz weitergeben.
DOI 10.5446/9601
Herausgeber Loviscach, Jörn
Erscheinungsjahr 2012
Sprache Deutsch
Produzent Loviscach, Jörn

Inhaltliche Metadaten

Fachgebiet Informatik

Zugehöriges Material

Folgende Ressource ist Begleitmaterial zum Video

Ähnliche Filme

Loading...
Feedback