18 lines
No EOL
2.2 KiB
Text
18 lines
No EOL
2.2 KiB
Text
= Automaten und Formale Sprachen
|
||
|
||
|===
|
||
|Zuordnung| AuS
|
||
|Klassenstufe| KS
|
||
|Bildungsplanbezug| BF, LF
|
||
|Werkzeug| BJ, JFLAP
|
||
|Autoren| L. Dietrich, U. Lautebach
|
||
|===
|
||
|
||
== Inhalt
|
||
Die sogenannten formalen Sprachen sind ein wichtiges Teilgebiet der theoretischen Informatik. Es beschreibt (in sehr mathematischer Prägung) Eigenschaften von Wortmengen, die als Eingabe von einem Informatiksysteme akzeptiert werden sollen. Eine solche Wortmenge nennt man „Sprache“. In der Regel muss das Informatiksystem mit der Eingabe eine Gültigkeitsprüfung durchführen („soll dieses Wort als Eingabe akzeptiert werden?“) und/oder die Eingabe in irgendeiner Form verarbeiten (also analysieren, in andere Form übersetzen o.ä.).
|
||
Es gibt viele Beispiele für formale Sprachen bzw. Software, die damit umgeht:
|
||
• Eingabefelder prüfen Mailadressen: Eine Eingabe wie „anna@mail.de“ soll akzeptiert, „annaQmail.de“ oder „anna@mailde“ aber sofort zurückgewiesen werden, weil das keine global gültigen Mailadressen sein können1. Eine gültige Adresse ist hier ein „Wort“, die Menge aller gültigen Mailadressen eine „Sprache“ im oben genannten Sinne.
|
||
• Webbrowser verarbeiten HTML: Der angelieferte HTML-Quelltext muss zuerst analysiert und interpretiert werden. Sind die Fragen „ist das korrektes HTML?“ und „was soll angezeigt werden?“ beantwortet, erzeugen sie schließlich eine bunte Bildschirmdarstellung.
|
||
• Compiler übersetzen Programme: Sie nehmen den Quelltext eines Programms entgegen, prüfen auf syntaktische Korrektheit und übersetzen es in eine andere Form, die der Computer (mehr oder weniger direkt) ausführen kann.
|
||
Mit den formalen Sprachen untrennbar verbunden ist die zugehörige Theorie der Automaten2, wobei Automat hier eher „Denkmodell“ bedeutet als „Maschine“. Es gibt unterschiedliche Klassen von Automaten, die einerseits mathematisch präzise beschrieben und untersucht werden; andererseits kann jeder Typ Automat jeweils einen bestimmten Typ Sprachen verarbeiten. Weil man sie zudem leicht in Software implementieren kann, sind sie in der praktischen Informatik extrem nützlich.
|
||
In ihrer Kombination sind formale Sprachen und Automaten ein Grundpfeiler der Informatik. |