Formale Sprachen, abstrakte Automaten und Compiler

1.1 TheoretischeInformatikundihreAnwendungen Zur Weihnachtszeit sind Flughäfen oft überfüllt und restlos ausgelastet. Jeder möchte rasch nach Hause in den Kreis der Familie. Weihnachten 2004 ging dieser Wunsch für ca. 30000 Reisende nicht in Erfüllung: Eine US-amerikanische Fl- gesellschaft musste über 1100 Flüge streichen. Grund war ein Softwarefehler. Ein enormer Image-Schaden für diese Firma war die Folge. Der Zwischenfall führte dazu, dass in den Medien über die Nachteile von Au- matisierung und Sicherheit im Informationszeitalter debattiert wurde. Wie war es aber zu dieser Katastrophe gekommen? Ein Mitarbeiter trug in ein Formular (v- mutlich ein typisches Web-Formular) einen Wert ein, der dort nicht hingehörte. Dies führte zu einer Kettenreaktion, die sich sogar noch auf eine weitere bekannte Fluglinie auswirkte, da die Server der beiden Fluggesellschaften von ein und der selben Firma betrieben wurden. Es gab kein Sicherheitssystem für einen solchen Fall. Mit sehr geringem Aufwand hätten die Entwickler des Systems einen solchen Fehler ausschließen können, nämlich durch eineEingabevalidierung. Hierfür sind Eingabe- Kenntnisse über formale Sprachen und abstrakte Automaten – ein Teilgebiet der validierung theoretischen Informatik – notwendig. Zulässige Eingaben werden dabei (durch formale Sprachen formaleGrammatikenoderabstrakteAutomatenbestimmtenTyps)exaktbeschr- und abstrakte ben, unzulässige werden ausge?ltert bzw. abgewiesen. Automaten Auch leistungsfähige Text-Editoren erfordern Theorie-Wissen, das sich nicht s- ten über Begrif?ichkeiten darstellt. Sie arbeiten nämlich mitregulärenAusdrücken reguläre und damit nicht nur Zeichen-, sondern Struktur-orientiert. Der Begriff „regulärer Ausdrücke Ausdruck“ wird hier mit der Erwartung benutzt, dass der Nutzer das zugrunde liegende theoretische Konzept kennt.