[Playlisten] [Impressum und Datenschutzerklärung]

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


CC-BY-NC-SA 3.0

Tempo:

Anklickbares Transkript:

so – die letzten Wochen des Semester soll ein Rundgang durch die Informatik sein – ?? ansatzweise erzählt was Datenstrukturen – sind – dickes Thema in der Informatik wenn man es komplett macht – er – sowas wie Warteschlangen – und Stack wir hatten – das – es bei Symmetrix auch noch – LWS können sich genauso zu Ostern gehören auch zu – dann ansatzweise – mal was zu Algorithmen – insbesondere – Sortierverfahren – Rhythmen – dass es – auch ein Thema mit dem man sich ein oder mehrere Messe auseinandersetzen – kann man es etwas tiefsinnige machen wir – uns – heute möchte ich einmal quer noch mal durch die formalen Sprachen – sprachen – und parallel dazu – etwas das anscheinend nicht damit zu tun hat aber lustigerweise doch sehr viel damit zu tun hat – die endlichen Automatenautomaten – das ist ein ziemliches dickes Thema in der theoretischen Informatik und Informatik an einer Uni studieren wenn sie da – gnadenlos mit gequälten – sie abstrakte Geschichte aber andererseits glaube der Teil den ich heute erzählen will – dann auch eine sehr praktische Geschichte – haben – die man dann doch für sehr viele Sachen verwenden kann – eine formale Sprache in der Informatik – soll einfach eine Sammlung von Zeichenketten – sein – Sprache – soll sein eine Sammlung von Zeichenketten – alle Zeichenketten die erlaubt sind die gültig sind in dieser Sprache – die korrekt sind in dieser Sprache und sonst keine Zeichenketten – wollten mit ihm gleich zwei Spiel Telefonnummern – angucken die formale Sprache die aus allen – in welcher Weise auch immer korrekt gebildeten Telefonnummern – besteht zum Beispiel null eins zwei drei vier fünf sechs soll so eine korrekt gebildete Telefonnummer – sein – eine ebenso soll null fünf zwo eins – eins zwei drei vier fünf sechs eine korrekt gewählte Telefonnummer sein – das wäre – die Sprache der korrekt gebildeten Telefonnummern was nicht dabei ist – heute so schreiben – an Telefonnummer die nicht Element ist Element durchgestrichen hat sich das – Rundschreiben damit klar zu lesen ist ?? mit durchgestrichen an die nicht dabei wäre es wäre zum Beispiel hundert zehn – die fängt nicht mit null an und hat kein Schrägstrich – sollte also – nicht von allgemeinen Telefonnummern – reden sondern ich sollte – von Telefonnummern – reden die man als – normaler Mensch – kriegen dann das meine ich damit – sollen alle mit Null anfangen sollen Schrägstrich haben – die Zahl nach dem Schrägstrich soll keine Null haben am Anfang – und so weiter das müsste man jetzt mal normalisieren – das es was ich mir unter dieser Sprache vorstelle die Sprache der – gebildeten – Telefonnummer – für – normale Leute – andere formale Sprachen werden – dann – sie nehmen alle korrekt gebildeten Webseiten – HTML Code – die erste direkt gewählte Webseite die zweite und so weiter es gibt unendlich viele korrekt gebildete Webseiten – große Sprache – die Sprache die aus allen gebildeten C Programm steht hier schon als Zeichenkette – ein komplettes Seeprogramm – das nächste komplette C Programm und so weiter und so weiter – bis ?? sicher – alle korrekt gebildeten Seeprogramme aufgelistet – Punkt das wäre – eine formale Sprache – in der Informatik und man sich einfach nur – an wie diese Zeichenketten – gebildet werden – wie kann ich das in Regeln fassen solche Zeichenketten zu bilden gibt's verschiedene Sorten an Regeln an an Komplexität – bei diesen Regeln – was folgt aus den Regeln was kann ich direkt ableiten – ohne tief in die Sprache reingeguckt zu haben ?? sowas guckt man sich an – es geht also um die Grammatik – so schön heißt es geht um die Grammatik von einer solchen Sprache – was ist korrekt gebildet und das ist nicht korrekt gebildet – ganz im Deutschunterricht – es geht nicht um die Semantik – kann sich die Semantik angucken an einigen Stellen aber hauptsächlich geht nicht um die Semantiksemantik – wäre Bedeutung – dass ich hier den Rückruf habe – das wäre Bedeutung oder dass das hier die Telefonnummer – von – Heinz Mülleis oder Wasser Komma das wären Bedeutung der hinter die guckt man sich bei den formalen Sprachen eher selten an – es ging größtenteils um die Grammatik das korrekte Bilden – von Zeichenketten – wobei – man natürlich dann auch nicht – auf die üblichen Zeichen beschränkte Sommertag danach ?? aus irgend einem endlichen Alphabet – sollen diese Zeichen – stammen – egal welches Alphabet das ist das chinesische oder alle mathematischen Sonderzeichen – dazu und so weiter – typischerweise wird das Alphabet schon das sein was man so – auf der Tastatur – darum geht's und ich möchte jetzt – diese Sprache hier der – einflussreichen – üblichen Telefonnummern – etwas – besser formalisierten – eine Möglichkeit dazu hatte ich in den – Videos gezeigt an Syntaxdiagramm – ich – möchte das so eine korrekt gebildete – übliche Telefonnummer – mit null anfängt – zu C null Sandbank Ringel Drummond zu sagen dass das – das ein Zeichen sein – ich möchte mit der null anfangen – und dann soll eine Zahl kommen – die keine null ist keine null null irgendwas keine Auslandsnummer – also wäre das jetzt – eine Zahl von eins bis – neun eine Ziffer vielleicht sogar eine Ziffer von eins bis neun – und danach – Können – weitere Ziffern kommen – und irgendwann kommt ein Schrägstrich – und danach geht es auch noch irgendwie weiter – dies mit den weiteren Ziffern wie kann ich das sinnvoll hinschreiben – das jetzt noch – beliebig viele vielleicht sogar weitere Ziffern kommen soll und fange damit an beliebig viele weitere Ziffern wie kann ich das auf mal ✂ die nächste Ziffer soll beliebig sein die – zweite Ziffer soll keine Null sein damit wenig mit null null Staaten – zur Rennstrecke noch – eine formal – Metternich mit null null Staaten – die nächste darf nicht nur sein Leben aus dem Grunde und hier würde ich alle Ziffern erlauben von null bis neun – was – kann ich nun veranstalten – damit es beliebig viele Ziffern von null bis neun werden können ✂ das ist der Trickeinfall – zum Schrägstrich – zur Wissens ?? Komma – einen Fall zum Schrägstrich – unentwegt – anschließend gleich den Schrägstrich – und einen – oben rum – das heißt jetzt so eine korrekt gebildete Telefonnummer fängt mit null an – dann kommt was von eins bis neun – dann kommt was von null bis neun und dann kommt ein Schrägstrich oder – nach dem null bis neun kommt – noch was von null bis neun – und ein Schrägstrich – oder noch was von null bis neun – dann ein Schrägstrich und so weiter das heißt die kann ich jetzt – beliebig viele – Ziffern von null bis neun noch – dazwischen pumpen das Komma weiterhin umso schöner machen beliebig viele Ziffern vor dem Schrägstrich es wird auch nicht schön aber – das wäre schon mal seine – erste Richtlinie weniger gebildete Telefonnummer aussehen soll – nach dem Schrägstrich soll sinnvollerweise nicht mit null weitergehen – an – die reine – Ortstelefonnummer – hier fängt auch nicht mit nun an das heißt die habe ich wieder was von eins – bis neun nur – was von eins bis neun – und danach – kann ich wieder was von null bis neun haben – und in dieser ersten – Annäherung – beliebig viel von der Sorte das heißt hier würde ich dann auch erlauben – einerseits das ich fertig bin – und andererseits – das ich das sie auch wieder in der Schleife haben kann nach dem Schrägstrich eine Ziffer von Uppsala – von – eins bis neun und nach der Ziffer von eins bis neun eine von null bis neun und eines Feierabend – sind sehr kurz die Telefonnummern ?? oder noch Vereine von null bis neun und noch eine von null bis neun noch eine von null bis neun des Landes – sowas ein – Syntaxdiagramm – insofern eine sehr spezielle Form eines Syntaxdiagramm – sagt das dasjenige komplett ausformuliert – ist die viel später noch kompetenter sind als Diagramme zeigen wo hier Platzhalter – eingesetzt sind – damit Komma dass die kompetente Sachen formulieren – das hier ist die – aller einfachste aller primitivste Form eines Syntaxdiagramm – komplett – überall – mit Symbolen belegt fertigen Symbolen aus meinem Alphabet belegt und nicht mit Platzhalter – dass es eine Art diese Sprache zu beschreiben jetzt kann ich sagen – welche – Zeichenfolgen – aus Ziffern und Schrägstrich anscheinend nur welche Zeichenfolgen korrekt gebildet sind – welche nicht zurückgebildet – sind alle korrekt gebildeten gehören zu dieser Sprache die durch diese Syntaxdiagramm – schrieben beschrieben wird – alle anderen gehören nicht dazu das ist eine Art seine formale Sprache zu beschreiben – an – der andere Artikel ich gleich auch tatsächlich dann mal vorführen in Software ein anderer dasselbe zu beschreiben nennt sich regulärer Ausdruck – der – kommt tatsächlich beim Programmieren gerne mal vor – insbesondere – das Internet Technik – am – ?? ist das in den üblichen Programmiersprachen – sofort eingebaut dieses Ding regulärer Ausdruck es darum geht festzustellen – ob ein bestimmter – Zeichenfolge – ein bestimmten Format genügt – verwendet man im allgemeinen dann reguläre Ausdrücke ist eine Telefonnummer – die jemanden sein Kundenkontaktformular – eingegeben hat wirklich eine Telefonnummer – untersteter Unsinn drin ist eine E-Mail-Adresse – eine E-Mail-Adresse seiner Webadresse eine Webadresse – sie von HTTP Doppelpunkt Schrägstrich Schrägstrich – ?? steht hinten was Punkt DE – und so weiter All das – kann man auf solche – Art – formulieren – und sagen wie eine korrekte Webadresse wie eine korrekte E-Mail-Adresse aussieht oder eine korrekte Telefonnummer aussieht ?? die üblicher das zu tun ist nicht mit Syntaxdiagramm – übrig hat das zu tun ist regulären Ausdrücken – an – so sieht das dann aus meiner – oben behalten – meine Telefonnummer – soll mit einer null anfangen – und jetzt habe ich eine Wahlmöglichkeit – von eins bis neun – schreibt man damit Klammern eins – oder zwei – oder und so weiter – bis neun eine Wahlmöglichkeit – irgendwas – aus den runden Klammern – diese einzelnen Abteilungen mit – geraden Strichen getrennt – und dann kommt was von null bis neun – davon – aber beliebig viel dafür gibt ?? Spezialsymbolsternchen – das einzige besondere was man braucht wird danach ein softwaregebautes – dann – ist wesentlich komplizierter man kann sowas hier von bis elegant hinschreiben man kann sagen – aber nichts – man kann Bereiche rausnehmen – und kann sagen – beliebig oft – aber nicht – null mal das sie nämlich ?? Problem wenn ich das so hin schreibe heißt das beliebig oft einschließlich – null mal – was nicht ganz korrektes – Sinnes muss er mindestens einmal kommen sofern sich das jetzt so schreiben – einmal – und danach beliebig oft einschließlich – null mal – so sieht das gerechter aus – muss ich einmal durch – und danach kann ich es wiederholen – einmal – und ?? Sternchen hast dann null mal – das – einmal das zweimal das sind dann an das wäre die Formulierung für den Teil vor dem ?? Schrägstrich dann kommt der Schrägstrich – und hinten geht es natürlich analog weiter – am Mittwoch eine Ziffer von – eins bis – neun und danach – mindestens einmal – und dann beliebig oft – einschließlich null mal Ziffer von null bis neun – Sternchen – sieht das – mit regulären Ausdrücken aus – ?? sagte man das dann der Seriensoftware gibt viel mehr Möglichkeiten – als nur den Strich – unter Sternchen – aber eigentlich geht das ganze zurück auf den Strich unter Sternchen alles andere ist dann nur Komfort – dieselbe Sprache wird beschrieben – durch diesen regulären Ausdruck – um – das kann manchmal in OpenOffice angucken – in OpenOffice kann ich reguläre Ausdrücke direkt in dieser Form verwenden ✂ so richtig man da – Ziffernfolgen – ein die Telefonnummern – sein könnten oder auch nicht ?? – Pages kann die Maschine – einfach aus einer Sprachbeschreibung – herausfinden – was eine korrekt gebildete Telefonnummer – ist – und was keine Gepäck gebildete Telefonnummer – ist das finden Sie bei den Suchen und Ersetzen Funktion aus – wo – man unter richtig gebildete – langweilig – sorgt – die erstes offensichtlich nicht richtig gebildet wegen des ABC ist da drinnen – die nächstes nicht richtig gebildet weil das von mich mit nur null anfängt dieses nicht richtig gebildet weil der Schrägstrich die davon kann nur verzerrt ihr so machen das nur ein Fehler drin ist als die null – da steht der Schrägstrich – die null ist okay der Schrägstrich zweites Falls so – vorsichtig unter Bearbeiten – Suchen und Ersetzen angucken Punkt – sie können suchen und ersetzen – mehr Optionen – regulärer Ausdruck – ähm sie können suchen und ersetzen in dem sie fest – Zeichenketten angeben indem sie sagen such mir alles eins null eins zwei drei hundert sechzehn null eins zwei drei – durch irgendwas – in der Form – aber sie können auch mit regulären Ausdrücken jetzt suchen wenn es da unten anklicken als hier mehr Optionen unter unten regulärer Ausdruck – besser guckt ob das was er da gefunden hat ?? Teil dieser Sprache ist aber das wieder erkennt – was jetzt passieren wird das alle korrekt gebildeten Telefonnummern – durch die Zeichenkettetreffer – ersetzt werden und suchen danach zu suchen einfach dem andern alle korrekt gebildeten Zeichen – im Text – groß das in üblichen Decksverarbeitungsprogramm – angewendet – haben in der Internetprogrammierung – verwendet man's eben dann um irgendwelche Eingabefelder zu prüfen hat jemand seine E-Mail-Adresse halbwegs plausibel eingegeben oder seine – Postleitzahl – sein Telefonnummer – habe ich plausibel angegeben hierbei den Text Verwaltungsprogramm – Wiens gerne ?? suchen und ersetzen – Punkt es gebe ich meinen Kram hier ein also – meine richtig gebildete Telefonnummer – soll anfangen mit einer null ?? – und dann soll – in runden Klammern irgendwas kommen von eins bis neun – das kann man – geschickter schreiben Sie Anbau man das geschickter schreiben kann aber das ist natürlich jetzt mal in so grundlegenden Form – Punkt sie legen – so – das würde heißen ?? mit den runden Klammern – nach der null irgendwas von eins bis neun – und danach den bitte was von null bis neun – ?? – aber beliebig oft – Sinn habe ich noch den einen verpennt das ich nämlich sagen muss okay einmal mindestens so hatte ich eine Syntaxdiagramm – gebaut – einmal mindestens was von null bis neun Gesetze mit unübersichtlichen – und danach – beliebig oft einschließlich null mal was von null bis neun – dann kommt ein Schrägstrich – dann kommt etwas von – eins bis neun – dann kommt wieder was von null bis neun und dann ?? beliebig oft was von null bis neun – wow – glaube ich gucke das immer raus sondern lediglich was er seine steht – das – der Städte also State mit null – dann eine Ziffer von eins bis neun – eins – soll und warte dann eine Ziffer von null bis neun dann beliebig oft eine Ziffer von null bis neun hundert Schrägstrich ein Ziffer ?? – und war heftig an – und jedes Mal wenn er eine Zeichenfolge – findet die diese Muster genügt dieser Sprache ist man in der Informatik sagen die Elemente der formalen Sprache ist – dann soll er das sich Treffer ersetzen – ich bin gespannt – ersetze alle – das auch okay – mach hier mal okay das jetzt – mit Andrew und – Anton Guido kucken können was passiert ist so – wie es erste Treffer – bis zum ABC – hier – ist das korrekt gebildet – deshalb – dachte ganz dreist okay bis zu dem ABC das ist der erste Treffer – und ersetzt die Zeichenkette bis zu dem ABC – man kann auf Verlangen – dass das wirklich dann mit einem Zeilenende aufhört will ich nicht vor versickern in dieser Eingabe auch wirklich verlangen – Ziffer Ziffer Ziffer und am Ende steht ein Zeilenumbruch – Punkt aber mal in die Doku dann wäre das hier verboten das noch ABC und so weiter in steter Bier findet ?? einfach eine gottgebildete – Telefonnummer und ersetzt das Gesetz weitaus der nächste Treffer sind das ist kein Treffer die zweite Zahl ist kein Treffer Klassiker nicht mit null an – vor dem Schrägstrich in der dritten Zeile – steht ein Treffer – den bis zu dem Schrägstrich ist es Craiggebildes – ?? mit null an – Schrägstrich und so weiter bis deines korrekt gebildet – das hier ist – nicht korrekt gebildet wie man sieht das nämlich nach dem Schrägstrich mit null an – der hier ist wieder korrekt gebildet und ?? es auch korrekt gebildet – das sind – reguläre Ausdrücke in Aktion für solche Sachen benutzt man das Suchen und Ersetzen bei der normalen Textverarbeitung – und meine ganzen Internetprogrammierung – um festzustellen ob irgendwelche Eingaben – plausibel sind – gut so sieht das in Aktion aus – ?? zwei Möglichkeiten dieselbe Sprache zu beschreiben einmal ihr Sonnen – Syntaxdiagramm – der primitiven Art und einmal – so einen regulären Ausdruck – Komma sie hat aber das kann man noch verfeinern – von Biss oder alle außer – Vernon und Jette noch in Zeilen und so weiter Defekten dutzendweise Spezialzeichen – in üblichen Programmiersprachen – und auch in Open Office und Konsorten – in der Informatik beschränkt man sich hier auf das oder – das Sternchen – das reicht – für alles andere alles andere ist dann nur Komfortfunktionen – sozusagen – und – das – lustige ist das man das jetzt auch noch etwas Drittes übersetzen kann – in einen endlichen Automaten – einer feinheitstechnischen – ?? endlicher Automat – dass es ihr überraschend bei Automaten – denkt man eher an Steuerungstechnik – da werden sie auch Automaten endlich Automaten in genau dieser Form auch massiv noch sehen – in der Veranstaltungstechnik – irgend eine Maschine – was gerade mit halber Kraft voller Kraft des Stopp – ist gestoppt oder muss gewartet werden und so weiter – ein Aufzug steht im ersten Stock im zweiten Stock – oder die Ampel steht auf rotgelb und so weiter endliche Automaten gibt's bei den Maschinen – extrem häufig Presse beschäftigen sich dann in der – Steuerungstechnik – mit endlichen Automaten – und in der Informatik – findet man – einen interessanten Zusammenhang zwischen – solchen Sprachen – und endlichen Automaten – diese Prüfung – ob so eine Zeichenkette – korrekt ist korrekt gebildet ist oder nicht Komma 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 – Syntaxdiagramm – in das Diagramm dieser einfachen ?? – an – soll das funktionieren – endlicher Automat – was es war ganz abstrakt auf hat Zustände – die man dann in der theoretischen Informatikkringel – malt es gibt andere Arten das allen UML – und ?? Standard hatte an etwas anderer das zu meiner Sissi Siedler steht – die theoretischen Komma die gemahlene Zustände mit Kringel – es gibt einen Startzustand – wenn ich Reset drücke – und dabei die Maschine an schalte – muss dieser Automat in einem ganz bestimmten Startzustand – sein – es gibt – Übergänge zwischen diesen Zuständen – die von irgendwelchen Ereignissen ausgelöst werden – die man drückt auf einen Knopf – und es vergeht soundso viel Zeit bei der Ampel – es gibt solche Übergänge – von ausgelöst – und dann gibt es man sich ?? mit diesen Sprachen beschäftigt auch in zuständigen – ?? gerne mit so doppelten Kreisen gemalt einzustellen – dies prüfen ob eine Zeichenkette Teil einer Sprache es funktioniert dann so – ich füttere diesen Automaten – mit der Zeichenkette – dieses Schreiben durch die verschiedenen Zustände – jeder mithilfe der Zeichen meiner Zeichenkette – das erste Zeichen ein A ist für dich von da nach Tagen zum Beispiel wenn das erste Zeichen ein Bees für die von der nach Tagen ebenfalls in das erste Zeichen an CS für die von da nach da gehen – wenn ich da unten bin und das kommt als nächstes ein Ar würde ich dahingehend – bin ich dahingehend – dass es mir seit sie für dich dahingehend und so weiter – also alle diese Pfeile schreiben sie – Buchstaben ihres Alphabets dran – und wenn am Ende der Zeichenkette in einem Endzustand sind dann lange die Zeichenkette ist okay – am Ende der Zeichenkette nicht in einem Endzustand sind sang die Zeichenkette ist nicht okay das wäre die Prüfung – einer Zeichenkette durch einen endlichen Automaten – diese Übergänge werden genommen wenn jetzt als nächstes ein bestimmtes Zeichen kommt – und das Ziel ist in einem der en Zuständen – zu landen – und sagt man Automat akzeptiert – die Zeichenkette – immer nicht am Ende der Zeichenkette in eine in Zustände ist Sackmann der Automat akzeptiert die Zeichenkette nicht – das ist – ziemlich abstrakt das kommende Sommer für die Telefonnummern – an – regulären Ausdrücken sieht ich muss irgendwo ein Startzustand – haben soweit kein Drama – anders geht's nicht – nur – was muss ich jetzt – als nächstes machen für mein endlichen Automateneinfall ✂ mit der null dieser Zustand hat jetzt nichts unbedingt eine – praktische Bedeutung diesem Fall wäre die erste Stelle – auf jeden Fall brauche ich einen Fall mit der null der sagt okay – wenn eine Null am Anfang ist dann komme ich zu irgendeinem anderen Zustand – und ich müsste doch noch – ganz streng bin sagen wenn irgendwas anders ist – komme ich zu einem Zustand in dem ich nach alle Fehler – weit sammeln kann – ähm – ich habe mal ganz dreist nicht nur dran – das ist mein Startzustand – wenn die null kommt – dann nicht da und da muss es weitergehen wenn da nicht die null kommt ?? irgendwas anderes – sagen landen wir da – und egal was da jetzt kommt ich mal so wirklich ausdrücklich dran egal was jetzt kommt – egal – landesweit immer nur in diesem Zustand wenn es nicht mit der null anfängt – nicht den klingender – wenn es nicht mit der null anfängt – ich da unten rein – und egal was jetzt kommt – man nicht weiter immer nur diesen Zustand – auf jeden Fall wird das eh kein Endzustand sein – wenn es mit der null anfängt – damit ?? weiter gucken okay – dann ist alles in Ordnung wenn jetzt was von eins bis neun kommt – was von eins – bis neun – und wenn nicht – eins bis neun kommt – dann – kann ich wieder unten hin marschieren – und versuchen von hier – in dem Zustand – als erstes kommt gleich Null meiner Zeichenkette – ich gehe in den Zustand – dann ?? sich das nächste Zeichen der Zeichenkette ein – wenn es nicht eins bis Neuner sage ich ob ich die in den Zustand – und damit einen hänge bleiben – ist die Zeichenkette durch – wenn es aber eins bis Neuner gehe ich in einen neuen Zustand – und – dann erwarte ich was von null bis neun – irgend eine Ziffer von null bis neun – wenn es nicht null bis neun ist sie wieder derselbe – null – bis neun ist muss ich wieder zu meinem Fehler – so – jetzt wird spannend jetzt möchte ich das aber wiederholen – können – was heißt das eigentlich – das ich diesen Schritt jetzt wiederholen können will ✂ und es geht noch einfacher als dass sie – das hier machen müsse ?? sowas haben wieder Sternchen für endliche Automaten – und in dieser Situation das lustigerweise dieses hier wieder Zustand bleibt auf sich selbst stehen wenn der jetzt was von null bis – neun kommt – und wenn nicht nur bis neun kommt – der geht jetzt für beide ja wenn nicht von null bis neun konnt – ich wieder in den Zustand der unten – also wenn ich da angekommen – bat ich das einmal null bis neun kommt – und wir Netsommer null bis neun kommt schön – lauf ich einfach im Kreisel – und jetzt muss der Schrägstrich kommen – wir sehen also nicht nur bis neun ist sogar falsch was ich da geziemt schreibe ich muss ein bisschen anders arbeiten wenn jetzt der Schrägstrich kommt – muss es auch erlaubt sein in diesem Zustand muss erlaubt sein das null bis neun kommt – oder der Schrägstrich konnte mit dem Schrägstrich – laufe ich dann ein zweiter – das heißt – hier gehe ich raus wenn – wir – das am besten – wie der – ?? Schrägstrich – noch – null bis neun – das gilt für diesen Fall in dem Zustand erwarte ich Ziffer von null bis neun – oder – den Schrägstrich – wow – und nach dem Schrägstrich – soll – eine Ziffer von eins bis neun kommen – also hier habe ich was von eins bis neun – mit den A neun Zustand – und wenn dann was anderes kommt – als eins bis neun – hier wieder zu meinem Fehler hin nicht eins bis – neun – Richter und Minister Lagarde gucken wenn ich da unten bin – ?? was vorher hatten eine Zahl von null bis neun und dann beliebig häufig eine Zahl von null bis neunundneunzig wird das weiter – mit einer Zahl von null bis neun mindestens eine – und hier noch mal eine Zahl von null bis neun – überlegen – ?? überlegen ob ich den hier schon – als Kringel machen kann – Komma zusammen überlegen ist das das ist das dieselbe Sprache wenn ich das hier Male ist das dieselbe Sprache wie ich sie oben hatte – dass ich hier aufhören mit einem Zustand – der dann – eine – durch Eingabe von null bis neun immer wieder in sich über vier führt wird und das dann ein Endzustand – ist wäre das dieselbe Sprache – hier oben beschrieben habe – hier will ich – nach dem Schrägstrich – eine Ziffer von eins bis neun dann eine Ziffer von null bis neun – und dann – keine Vereine – oder so zu viel – ?? noch mal Ziffern von null bis neun – das ist – aber nicht infrage das es lustigerweise nicht diese Sprache hier was ist der Unterschied zu meinem – meine sprach von ?? ✂ ein Endzustand darf wiederholt – werden darf der ?? darf auch nach dem Endzustand wieder in andere Zustände zurückgehen wichtig ist nur wenn die Zeichenkette durchgelaufen – ist das dann die Maschine in diesem Zustand steht wenn die Zeichenkette lautet genau dann wenn Zeichenkette erlaubt ist ✂ was mir jetzt fehlt ist das nach der eins bis neun – mindestens einmal noch null bis neun kommen muss so wie ich das in den Syntaxdiagramm – aufgeschrieben habe hier – muss er mindestens einmal null bis neun kommen soll Komma klarmachen dass dieser Fall so rum läuft – mindestens einmal muss null bis neun kommen – das – passiert hier nicht – eins bis neun – bin ich in dem Endzustand – in meine Zeichenkette da aufhört – bin ich im Endzustand und sie wird akzeptiert – ich hätte nicht immer zwangsläufig – eine weitere Ziffer von null bis neun des erforderlichen noch einen weiteren Zustand das kann nicht der Endzustand sein – auf einen weiteren Zustand – also hiermit Ziffern von null bis neun wird in ein weiteren Zustand das ist der Endzustand – und der Licht in der Schleife wenn ich nach dieser Ziffer von null bis neun noch weitere Ziffern habe von null bis neun keine Aktion bleibe ich in diesem Endzustand – und – gucken eins bis neun ?? wieder raus wenn ich hier nicht – null bis neun habe – hier wieder zu diesen Fehler gehen und wenn ich hier nicht nur bis neun habe – müsse ebenfalls zu dem Fehler gehen – in – der – Informatik kann man dann – einen Tag drauf verwenden – zu beweisen – dass die Sprache die man so beschreiben kann – genau die selben sind die man so beschreiben kann mit regulären Ausdrücken denen sich dann die regulären Sprachen – ist nicht so wichtig an dieser Stelle – nicht vor die Finger vorführen – was für Arten es gibt Sprachen zu beschreiben – also eine – übliche Art dann – ist praktisch auszudrücken – sind reguläre Ausdrücke – insbesondere weil es viele Programmier sprachen eingebaut ist – und eine ganz andere Auffassung die man ihm in der theoretischen Informatik entwickelt sind diese endlichen Automaten – eher – ich prüfe eine Zeichenkette – mit so einer Maschine – Maschinisten – eben keine Ampel und keine Druckerpresse – und kein Aufzug sondern eine Maschine die Zeichenketten prüft warum nicht – und – der Gedanke ist die Zeichenkette – muss dafür sorgen dass diese Maschine durch – ihre Zustände läuft jedes Zeichen Leerzeichen geht es quasi eine Eingabe – durch den Club null drücke den Knopf – fünf drücke den Knopf null und so weiter jedes Zeichen ist eine Eingabe – und ich frage mich zum Schluss – steht diese Maschinen einen der Zustände – die ich als in Zustände markiert habe ein Jahr dann ist die Zeichenkette – korrekt – wenn nein dann ist die Zeichenkette nicht dass wir gezielt – ein Automat – der meine etwas komische Sprache der gebildeten Telefonnummern prüft – an – dieses Ding gab's ja so ungefähr auch schon mal als Seminaraufgabe – der was bisschen komplizierter hier des die Anzahl verfestigte – dich – jetzt nicht – bis dahin durchführen – und der meßprogrammiermäßig – sehr zu Fuß gelöst – werden – ?? ad hoc wie man das so nennen Ziffer Ziffer für Ziffer durchgegangen – über Licht überprüfen kann wie man zählen kann sobald man auf diese Abstraktion – hier ist – mit regulären Ausdrücken und endlichen Automaten – kann man es sehr systematisch – angehen man kann jetzt tatsächlich diesen endlichen Automaten – einfach programmieren – und damit prüfen ob irgendwelche Zeichenketten – Telefonnummern – in diesem speziellen Format sind – das geht dann ziemlich endlos durch – wenn sie – einmal dieses – Diagramm auf gemalt haben – an – sich wird mal einfach die Zustände jetzt durch nummerieren – den die Zustände als solche sind nicht so richtig sinnvoll – der hier naja gut das hat etwas mit Fehler zu tun – ihr Zustand aus mit akzeptiert zu tun – am – das ist der letzte vor dem Schrägstrich der erste vor dem Schrägstrich – mit – etwas – Mühe kann man den schon Bedeutungen geben aber eint ich sie mir gar nicht überlegen was die Bedeutung dieser Zustände ist – ich hab jetzt einfach – hier Übergänge – Ereignisse und das ganze – baulich in einer Tabelle zusammen und die Tabelle programmiere ich dann – also – wieder mal Durchsage – Zustand null eins zwei – drei – drei – vier – fünf – sechs – sieben Komma ?? – you – das sind also acht Zustände insgesamt die schmeiße gleich einfach in eine Tabelle – und in der Tabelle steht dann was diese wie sich diese Zustände weiter entwickeln sollen – wenn bestimmte Eingaben kommen – sehen was wir haben können und ich muss gucken ob – die Eingabe nur lästig muss gucken ob sie eins bis neun ist ich muss gucken ob sie ein Schrägstrich ist – oder alles anderer – eigentlich habe ich effektiv nur drei Eingaben – ist die Eingabe null ist die Eingabe – eine Ziffer von eins bis neun – Ziffer ein Schrägstrich – oder alles andere – mit – drei Fällen ebenso natürlich vier Fälle das sind die vier Fälle dich bei den Eingaben unterscheiden muss – und euch dann einfach in C eine Tabelle – die das ganze – vor – Arztes – die wir dann so aussehen – glaube letztes Jahr hatte ich die andersrum gezeigt man ganze Tabelle andersrum aufbauen – haben – jetzt – vorschwebt – die Tabelle aufzubauen – ist folgendes – das hier in der Spalte links – die Eingabe steht also null – eins bis neun – Schrägstrich – und alles andere – und das – auf der – x-Achse – der horizontalen – Achse die Zustände stehen von null – bis – sieben wir Komma – dann schreibe ich auf diese Kreuzungspunkte – folgendes – wenn ich im Zustand zwei bin – und es kommt als Eingabe eins bis neun – schreibe ich hier was passieren soll – auf die jeweilige Kreuzung wenn ich im Zustand zwei bin und es kommt eins bis neun schreibe ich da rein was der nächste Zustand sein soll – weiter gucken wenn ich in Zustand zwei bin – Zustand zwei Wind es kommt – eins bis neun – Teilmenge davon gehe ich zum Zustand drei – tausend drei rein – für die Tabelle aus – und schmeißt das dann in sein Programm rein – und das Programmpaket – einfach durch die Tabelle durch es weiß – bin im Zustand so zu vier – jetzt kommt die Eingabe soundso – also muss ich dann in den Zustand soundsoviel gehen und ganz am Ende guckt das Programm ob sie meinte in Zustände ist diesem Fall nur – Zustand sechs ist – in der Tat die null geht auch des also wenn hier die null kommt – in der auch hier den Zustand – Nummer drei – ich hab die auseinandergehalten – hier die null und die eins bis neun – um möglichst wenig – eher – Ereignisse zu haben – eigentlich ja nur vier Eingaben – und hier sage ich eigentlich – ja eigentlich habe ich ihr dann zwei Eingaben – durch das Somali nicht habe ich ein nicht Eingabe ?? neun oder die Eingabe null – so wäre das ein ganz streng auf gemalt – Punkt – der Einfachheit halber lass ich mal so von null bis neun – gibt's jetzt zwei – Ereignisse die von zwei zu drei führendes eigenes Null sein eigenes eins bis neun ✂ so der erste Job ist jetzt diese Tabelle in C zu gießen – meine Zustände aber schon ganz dreist durchnummeriert – von null bis sieben – dieser – Eingaben – könnte man jetzt mit einer enum machen – dass sie wirklich was benanntes haben sie roh – und schon ein – Flash – eines Engels oder sowas – am ?? für die jetzt auch einfach mal um es ganz schlicht zu haben – durch nummerieren null eins zwei drei – römisch insgesamt ein – zweidimensionale – Sylvain – und in diesen zweidimensionalen – Weg stehen einfach Zahlen an welcher Zustand wird als nächster – angenommen – sich sogar als Schar vielleicht – zu viele Zeitschar – ein zweidimensional – te es ist – acht breit – schon – und – vier hob – die äußerste Dimension müssen wir nicht angeben ?? göttliche Vieh reinschreiben – Punkt das kann der Compiler selbst hinkriegen – Sonett – in – jeder Zeile acht Sachen drin stehen – acht – von vier Stück – oder – so den hat man netterweise schon – in – der – Spalte mit der Nummer zwei muss das losgehen mit drei dreiviertel ?? die noch zu ändern – wenn im Zustand zwei ein Schrägstrich kommt – Zustand zwei – ein Schrägstrich kommt – in zum sieben – ?? den Zustand zwar irgendwas anders aber kommt gehen wir zu sieben ?? das muss alles – sieben – sieben sein – Herrchen eintragen drei drei sieben sieben – in der Spalte Nummer zwei – Spaltennummer zwei – drei drei – sieben – waren – es gibt noch ein Ding das man sofort komplett eintragen – kann – wenn ich im Zustand sieben einmal gelandet bin – dann soll ich nie wieder rauskommen – aus egal was passiert egal welche Eingabe kommt im Zustand sieben – ich muss wieder – in Zustand sieben landen – es heißt das für diese Tabelle – wenn ich im Zustand sieben bin und dann kommt die null solchen Zustand sieben bleiben wenn ich Zustand sieben bin und es kommt ein ?? bis neunzehn und so weiter hinten soll es immer auf der sie bleiben ?? auch noch geschenkt – muss es überall sieben sieben sieben sieben heißen – gucken ob richtig gezählt habe eins – drei vier fünf sechs – sieben – acht einer zu viel – so – wie geht's weiter wenn ich im Zustand null bin – dann kann es nur mit der null weitergehen – das es das erste mögliche die erste mögliche Eingabe in der ersten Zeile – nur oben steht bei der null die eins ansonsten steht überall die sieben – eins – ansonsten steht über sieben – wenn – ich bei der A eins bin – geht es nur – mit der eins bis neun weiter und ansonsten – immer zum Zustand sieben eins bis neun war – die zweite Zeile – ergibt also wenn Zustand eins in der zweiten Zeile was ansonsten muss ich immer dritte sieben Ändern – der zweiten Zeile steht bei der einst die zwei ansonsten die sieben – zwei und ansonsten die sieben – Zustand Nummer zwei null eins zwei hatten war jetzt kommt der Zustand Nummer drei – männlichen Zustand Nummer drei bin jetzt schwierig – bei der null bei der eins bis neun das eine Id zwei verschiedene Eingaben – bei der nur bei der eins bis neun – geht's wieder in drei – beim Schrägstrich geht's ins vier – ansonsten – geht's in sieben – also – erwiesene Zustand selbst zurück – eines null ist geht's in den Zustand selbst zurück – besser eins bis neun es geht in den Zustand selbst zurück – wenn's ein Schrägstrich Wagens in den nächsten und wenn es alles andere war GC mein Fehlerzustand – das waren null eins zwei drei der Zustand Nummer drei hundert Zustand Nummer vier – wenn es nach eins bis neun ist das ?? der zweiten Zeile gehe ich zur fünf und ansonsten ?? ich immer zu sieben – wenn es nach eins bis neun ist der hier gehe ich zur – fünf und ansonsten immer zusätzlichen – Netz kommt der Zustand Nummer – fünf – Beistrich – kann also die null erlauben und die eins bis neun ?? sind die ersten beiden seinen ersten beiden Zeilen steht eine sechs – und ansonsten steht die Sieben – steht eine sechs – steht ein sieben – und der Zustand mit der Nummer sechs – der hier – bei der null – ?? für die sechs oder eins bis neun steht die sechsten ansonsten steht die sieben – da steht die sieben das ist die Tabelle – Sinn hat es auf diese – Art – so ein Diagramm – nicht – so ein Diagramm jetzt umgewandelt – in eine Tabelle – mit einfacher Zahlen stehen ich schreibe einfach wer auf welche Weise womit verbunden ist in die Tabelle rein – und mein Programm – verarbeitet – jetzt diese Tabelle des weiß überhaupt nichts von Telefonnummern – und was auch immer es sieht nur diese Tabelle – was – jetzt an der Tabelle rum als ich doch irgendwie mal eine – Zahl mit Steckers – ausprobieren kann und eine Zeichenkette – genauer gesagt erstmals das eine Zeichenkette – durch das ausprobieren kann nach ?? sollte das ganze war natürlich hübsch in irgendwelche – Funktion verpackt sein und eignet sie Dateien und Header-Datei verpackt sein Herz noch – bisschen alles – unschön gelöst was was die Programmierpraxis – davon sie angeht mich interessiert jetzt wirklich nur – die man damit umgehen kann ich das – hübscher macht sauberer machen als ich die Männer Zeichenkette rein – so – jetzt möchte ich diese Zeichenkette – prüfen – das heißt – muss diese Zeichenkette – Buchstabe für Buchstabe – ablaufen – und – in dem – Automaten hier weiter schreiten – was muss ich jetzt – wie Tun wie kann ich jetzt weitermachen ✂ also durch diese Zeichen jetzt durchzugehen – ich will ja ein Zeichen nach dem andern – Reinfüttern in den Automaten – im sinnvollerweise – eine for-Schleife ich weiß wie viele Zeichen es sind es geht schon in einer Schritten – das Wirkung ?? das Intervallschleife – macht irgendwo muss jene for-Schleife stehen – nur – kleiner – ist nämlich natürlich auch – die ganze Zeit der Name – zur – sollte diese Zeichenkette auch mit einem Namen versehen – ?? als sie – eher maximal – die Länge – meiner Zeichenkette A – und denk längst zu haben brauche ich jetzt – Kara – Header-Datei – und in einer Schritten – in einer Schritten – und in der Schleife will ich jetzt Zeichen Anzeichen – in den Automatenfilter – an – ich muss mir merken – wo ich gerade bin im Automaten – welcher Zustand gerade angesagt – ist – und dann guck ich in der Tabelle nach zuwegen zuständig gehen muss – wie merke ich mir welcher Zustand gerade angesagt ist – genau sich zu merken wo sie gerade sind – in dem Gestrüpp welcher der Zustände gerade angesagt ist – es einfach ein Kind merken was ist die Nummer des Zustands wenn diese Zustände jetzt hier hübsch benannt hätte mit einer enum – von wegen Start und Ende und Fehler und – vor dem Schrägstrich nachdem Schrägstrich – dann – würde ich eine enum eben niemals – Typ der variabler Wiederbeschaffung durchnummeriert – ?? entnehmen – oder analog zu der Tabelle Dichte hatte er gesagt an sein Schar – gesondert Zustand zum anderen stehen deshalb ?? – an sein Schaf für die – Nummer des Zustands – in dem ich gerade bin – RZ – und der Anfangszustand – sinnvollerweise – weiter sich auch der mit der Nummer null – besserte sich das auf die Nummer null und gucke jetzt was passiert Z soll – enthalten in welchem Zustand ich gerade bin – ich guck mir das nächste Zeichen an und gucke dann in der Tabelle nach zu welchem Zustand ich jetzt muss – okay – Voicebar – das nächste Zeichen müsse sich relativ – einfach erst mal aus dieser Zeichenkette – das Zeichen an der Stelle I bekommen Sie daran ✂ zu A in eckigen Klammern hier die Zeichenkette ist ein Püree aus diesem Array gibt mir das soundso fehlte Zeichen raus und jetzt will ich feststellen ob dieses Ding eine null ist oder an eins bis neun ist – oder ein Schrägstrich ist oder irgendwas anderes – an der Summe nachher dann die Nummer hier der Zeile sagen Pensionist möchte ich in der Zeile mit der Nummer null nachgucken wenn's eins bis neun ist möchte ich in der Zeile mit der Nummer – eins nachgucken wenn sie Schrägstrich es neue Zeile mit der Nummer zwei – und wenn's alles andere ist in der Zeile mit der Nummer drei – das muss irgendwie übersetzen ich baue mir eine Variable – einen vielleicht die verwegene ein Verwegenereignis – oder sowas in die – Augen – vielleicht kann ich Initialisierung – das klarzumachen also – wenn – mein aktuelles – Zeichen – aus der gerade angesagt – ist – die Ziffer null ist so muss es dann ja aussehendes – Zeichen – war von ihr ist identisch mit der Ziffer null ?? nicht – die die einfachen Anführungszeichen Vergessens ist ja nicht in Symbol Nummer gleich null sondern diese Symbolnummer – ist dies Nummer des Symbols – null – wenn das der Fall ist dann habe ich das Ereignis mit der Nummer null die Eingabe mit der Nummer null – acht – sind die Schweifklammer noch dieser Maschine – wenn – man aber ganz was – ist – wenn – Valentin – sonst – wenn das nicht – nur Listen jetzt muss ich irgendwas haben eins bis neun – wenn das eins bis neun ist – dann merklich mehr die Nummer meines – Ereignisses ist eins – können Sie das ausformuliert – möcht jetzt prüfen ob das – Zeichen was ich kriege eine Ziffer von eins bis neun ist ✂ tatsächlich – zwischen diesen beiden kurz einschließlich – es ist größer gleich den Zeichencode – für die eins Mozilla für die eins – und es ist kleiner gleich den Zeichencode für die neun dann habe ich – eine Ziffer zwischen – einer gleich eine Ziffer zwischen eins und neun – so und merke mir das ist das – Ereignis – mit der Nummer eins – und wenn es – der LC freute sich alle ausschließen gegenseitig – könnte das Geld auch weglassen sieht ein bisschen unschön aus mit dem L zwanzigster – diese Fälle schließen sich alle gegenseitig aus es im Prinzip auch bisschen schneller – aber der wesentliche Effekt ist dass sie allen Leuten die dieses Programm lesen mitteilen – dass sie sich bewusst sind das diese Fälle sich gegenseitig ausschließen – so wenn es ein Schrägstrich ist dann merke ich mir – einen zwei – und – ansonsten – ist es alles andere und ich merke mir eine drei – so könnte man das aufschreiben das es jetzt das übersetzen von – diesen Eingabemöglichkeiten – null – eins bis neun Schrägstrich – alles andere – in eine Zahl – null zwei – könnt es auch etwas eleganter machen statt es hier hinten – noch das Els in der Bauern – können Sie erfahren auch sofort sagen wir nehmen erst mal an es ist alles andere – eh gleich drei – und prüfen nur noch die null eins bis neunten Schrägstrich – ich finde es jetzt so auf Anhieb übersichtlicher – heißt dass ich alles erwischt habe – und jetzt kann ich in meiner Tabelle nachgucken – meine Tabelle sagt mir – der – ?? die erste Koordinate – hier – nimmt die Nummer des Ereignisses – das ist das eh die zweite Koordinate – nimmt den aktuellen Zustand – und was rauskommt ist der nächste Zustand – was – schreiben Sie hin – um jetzt zu zu schreiten in diesem – Automaten ✂ irgendwie muss jetzt ja genau der Tabelle nachgeguckt – werden die hieß – Berger – nahm sehr schön – ?? – so soll das heißen – AEZ Maschinen soll man Tabelle heißen in dieser Tabelle guck ich nach der erste – ist die Zeile das ist das Ereignis unserer gerade rausgeprügelt – haben – man – muss auch nicht was den von FS ähm – EE – und hinten steht der alte Zustand – Zustand – null – erste Spalte – Zustand – eins zweite Spalte – und so weiter so war das zu verstehen was mache jetzt mit diesem Ergebnis was mache ich mit dem was sich aus der Tabelle ausgelesen habe ✂ genau das ist der neue Zustand sie weisen das einfach Z zu simpel sie das heraus das ist der – endliche Automat wenn sie einmal als – Tabelle formuliert haben – ich – habe gerade aus der Zeichenkette – entnommen in welcher Zeile ich bin – ist die Zahl null gekommen ist die Zahl eins bis neun gekommen Ziffer eins bis neun gekommen ist Schrägstrich kommt es was anders gekommen ich weiß in welcher Spalte ich bin dass der aktuelle Zustand – jetzt ruhig auf der Kreuzung nach und was ist der nächste Zustand ist – das einfach zeitgleich – sowie finde ich jetzt Herausfilme fertig sind – ob denn – diese – Zeichenkette – die ich am Anfang gegeben habe ob diese Zeichenkette – jetzt auch wirklich diesem Format genügt hat – was muss ich jetzt machen – genau das ist der Trick wenn wir fertig sind mit der Zeichenkette nur die abgearbeitet haben kuck ich einfach ob ich jetzt den Zustand Nummer sechs bin – der einzige Endzustand ich gucke ob ich in irgendeinem der Ent zustehende Sendung ja nur eine Nummer sechs wenn ich da gelandet bin ?? Zeichenkette okay bin nicht weil sie nicht okay – Punkt hier schreibe ich es einfach griff – zeitgleich – sechs – einfach – aus korrekt – und ansonsten gebe ich aus das es nicht korrekt war – natürlich auch jetzt für das Kind F noch hundert bei Unionssohnes – Komma Fehler suchen ?? ich bin gespannt wie viele der jetzigen ✂ genau damit den ersten – das ist ja wahr was ich geschrieben habe das aber nicht seh was ich da geschrieben habe soll – das – Fenster – die eckigen Klammern hinter das – hinter den Variablennamen – sehen – aber gucken was der Compiler bei Satyr – Mac – ein Fehler immer noch – die zu lang waren – das heißt ich sollte man einen Tipp einstellen – denn bisschen mehr Speicherplatz hat – Jan – Erik – Komma – für dreißig X – Komma der müsse mehr Speicher hat – ?? – okay – der kann das fressen – das heißt – grammatisch – ist das jetzt okay das ist ja genau das was jemand auch gesagt habe zu – formalen Sprachen – der Compiler findet das okay das ist also grammatisch okay ob es das jetzt tut was ich will ?? ganz andere Sache – semantisch richtig ist – an – neunzehn – Verlassens verlaufen – und ich brauche nicht diese sämtliche eines Terminal – zu – führen Punkt – ?? – okay – zu dieser Telefonnummer sagte mir korrekt – gespannt – wenn ich ihren zweiten Schrägstrich einbaue – ?? – sagte nicht korrekt – ?? müssen ein hundert verschiedene Fälle mal durch Nudeln – was ist wenn ich mich mit der Nullstarter – das – kann natürlich ?? automatisieren – es gibt dann auch Bibliotheken mit denen man genauso was automatisieren – kann Unit Tests – sie schreiben – hundert oder tausend Testfälle auf und was jeweils rauskommen soll und die Biotechnologie – automatisch durch – ?? nicht korrekt gefällt mir auch ✂ zwei – Sachen eingebunden Swing habe ich unten mit F benutzt habe zur Ausgabe ?? Standard Alko – weil ich – hier – die Länge der Zeichenkette benutzt haben – ?? nicht zu Ende testen einfach – einfacher Zahlen eingeben – ist ja nicht so gerade – die seriöse Art das zu testen müsst es wirklich sauber durch testen – alle möglichen Kombinationen – mal ausprobieren – so sieht das dann beim Programmieren aus und sie sehen dass das im Unterschied zu der Seminaraufgabe – oder was ähnliches hatten Telefonnummern – erkennen – ob sie das richtige Format haben – dann – durch die zu dieser Seminaraufgabe – ist das ein komplett – anderer Art anzugehen – total formaljuristisch – ich schreibe eine – Sprache – abstrakt hin was ist diese Sprache – der korrekten Telefonnummern – übersetzte das in einen Automaten – ersetzt den Automaten in eine Tabelle – sehen was jetzt passiert auf einfach nur noch diese Tabelle durch das ist alles hier die mir das interessiert mich – an das es wesentlich leichter zu beherrschen ?? beim Programmieren als wenn man ad hoc sich über Licht Autismus dieses Zeichen kommen und da muss jenes Zeichen kommt – an – das es viel leichter zu verstehen – vielleicht dazu verifizieren – auch – ein vielleicht überzeugendes das richtige tut – Zeit verkraften zu so einer Lösung – und das hübsche das ehrlich hier schon mit OpenOffice gezeichnet hübsche ist in dieser Form mit den – regulären Ausdrücken – ist es sowieso die meisten Programmiersprachen – eingebaut führt sie gibt Bibliotheken die sie dazu laden können die dann auch sowas verstehen der Müßiggang selbst programmieren und beschreiben nur abstrakt hin – wie die Sprache funktioniert – die wieder haben wollen – abschließend noch mal soll ich zeigen dass die Sprachen von dieser Art hier dehnen sich die regulären Sprachen sprachen diese mit regulären Ausdrücken hinschreiben können und mit – endlichen Automaten – testen können diese Sprachen – sind – nicht gerade sehr – aussagekräftig – sie nicht gerade sehr vielseitig – was man zum Beispiel nicht prüfen kann mit solchen Sprachen – ist auf Klammern auch wieder zugemacht werden wenn es beliebig viele Klammern sein dürfen wenn sie eine Sprache bauen wollen – in der Sauce ausgeklammert werden kann und dann wollte dafür sorgen das auch immer genauso auf die Klammern wieder zu gehen – gibt das ein Problem mit diesen regulären Sprachen – wenn ich erlauben will dass es hier beliebig viele endlich aber beliebig viele Klammern sein dürfen kann ich das nicht – mit einem – endlichen Automaten prüfen – ärgerlicherweise – also das ist – an – eine ganz dicke Limitierung – dieser Spiel – waren die man so darstellen kann mit regulären Ausdrücken und mit endlichen – Automaten dann prüfen kann – muss gerade noch mal überlegen warum kann man das nicht – mit so einem Automaten prüfen – was haut da nicht hin – wenn ich – sicherstellen – will dass diese Sprache – wieder vorne – tausend Klammer auf hat auch genau tausend Klammern wieder zu hart – oder wenn sie von eine Million Klammer auf hat ein da hinten auch genau wieder eine Million Klammer zu – was ist das Problem wenn sie einen einzigen – endlichen Automaten hin meint der das prüfen können soll – genauso viele Klammern wieder zu gehen wie vor aufgegangen – sind ✂ sie haben sofort eine praktische Lösung für das Problem sie zählen einfach die Klammer mit – vier aufwärts und der abwärts das dumme ist das so ein – endlicher Automat nicht beliebig zählen kann der hat ja nur endlich viele Zustände – der kann deshalb nicht beliebig hoch zählt das Problem ist – folgendes mit dem Zählen sollte man es wirklich dumm das sieht man daran der kann nicht beliebig mitzählen – an – der Musna – die erste Klammer hat einen anderen Zustand seinerzeit die zweite Klammer hat das er nachher auch wieder zurück – feststellen kann ob er den zwei oder eine Klammer auf wenn die dritte Kammer da kommt müsse noch einem anderen Zustand sein in die vierte Klammer kommt muss er noch im anderen Zustand seit um nachher wieder feststellen zu können das den vier Klammern – nötig sind und nicht drei Klammer nötig sind – das heißt wenn sie verlangen – das System hier eine Million klammern auf ?? – annimmt und ähnlichem erzählt das es auch wieder eine Million Klammer zu geht brauchen sie mindestens eine Million Zustände – wenn sie verlangen – dass die Zahl der Klammern ihr beliebig sein darf endlich aber beliebig sein darf – wie das nicht funktionierende – System ist unendlich groß eingescannt ein endlicher Automat das prüf ?? es gibt eine billige Lösung – sie zählen einfach die Klammern aber endlicher Automat kann das nicht und weil der endliche Automat das nicht kann – an – geht es dann auch hier mit den regulären Ausdrücken absurderweise nicht ✂ es – gibt eine allgemeineres – Argument das kommt in der theoretischen Informatik dann vor – hört sich monströs an das Padding Lemma – Spampinglemma – für reguläre Sprachen – sie mangels Serien – denkt der oder die sie studieren Raketentechnik – am Dilemma für – Sprachen – versprachen dieser Art – an wenn ich so einen Automaten habe – und ich jeder mit einem sehr sehr langen – Wort rein – aus mit einer sehr langen Telefonnummer – jeder rein dieser Automat – läuft durch die Gegend – was muss irgendwann passieren wenn das Wort sehr lang ist mit dem ich eingeht ✂ Klammer auf wenn Sie sich vorstellen dass ihr Automat – Angela – zehn Zustände sowas hat – eine Million oder eine Milliarde eine feste – endliche Zahl von Zuständen hat und jetzt gehen Sie mit einem super super superlangen – Wort einer super langen Zeichenkette darein – in diesen endlichen Automaten – wann muss was passieren ✂ irgendwann – irgendwann muss dann eine Schleife kommen das ist der Witz irgendwann muss ich das Ding – wiederholen irgendwo muss dann Schleife drin sein wenn sie mit einer Million Zeichen reingehen und dieses Ding hat nur tausend Zustände – muss ich irgendwo Schleife ergeben – wenn denn – diese Zeichenkette mit einer Million – Zeichen erlaubt es also wenn sie so eine lange Zeichenkette erlauben – tatsächlich in der Sprache – muss in diesem Automaten – eine Schleife drin sein und das hat sofort eine Folgewende – ein Schleife drinnen ist – als das ich kann diese Schleife – einmal durchlaufen zweimal durchlaufen tausend Mal durchlaufen zehn tausend ?? durchlaufen auch all das muss erlaubt sein – das es diese sogenannte Pappenlemma für reguläre Sprachen es gibt auch noch in anderes für – andere Sprachen – ähm – wenn diese Sprache ein Wort enthält das lang genug ist – dann können Sie dieses Wort in drei Teile teilen – und – dieser Teil in der Mitte den können sie beliebig wiederholen – weil das einfache Schleife sein muss Sie müssen mindestens ein Schleife drin haben und der Teil des Worts – der Zeichenkette – in der Schleife läuft den können sie beliebig oft wiederholen und auch das muss wieder erlaubt sein als wenn das ABC – ist – und dass ein erlaubtes Wort ist dann muss auch dieses hier A – B – B – C ein erlaubtes Wort sein ich wiederhole einfach die Schleife und es muss – A und den jetzt dreimal B – zehn – ein erlaubtes Wort sein wenn das geht muss das Gehen und das Gehen und so weiter – wir teilen der Schleife muss beliebig oft wiederholbar sein und auch wieder erlaubt sein – das ist eine – Eigenschaft von diesen regulären Sprachen hier – und das schließt ganz viele Sprachen sofort aus – weil eben nicht einfach in jeder Sprache so ein Bestandteil plötzlich wiederholt werden darf beliebig häufig – regulär sprach ?? sofort die Eigenschaften sie sehr lange Wörter drin haben – Punkt gibt es darin Teile die beliebig wiederholt werden dass er sich pampig auf Pumpen – Punkt hier – das erlaubte Wort ?? Bestandteile auf