Druckversion vom 05.05.2024 13:09 Uhr
Startseite Qualifikationsphase Theoretische Informatik Formale Sprachen
Formale Sprachen
Computerlyrik
Der Mann verfolgt die Frau.
Der Hund beißt die Frau.
Die Katze beißt das Kind.
Der Hund verfolgt die Frau.
Die Katze ruft das Kind.
Die Katze verfolgt die Frau.
Der Mann ruft den Briefträger.
Solche Nonsensgedichte kann man mit einem kleinen Java-Programm erzeugen, wenn man eine Liste von Subjekten, eine Liste von Prädikaten und eine von Objekten angibt, Elemente zufällig auswählen lässt (Math.random()) und zeilenweise ausgibt. Ausgefeiltere Gedichtgeneratoren findet man, wenn man im Internet nach „Computerlyrik“ sucht.
Grundbegriffe, Grammatiken
Grammatiken dienen dazu, formale Sprachen zu beschreiben. Dabei gibt man nicht an, wie ein fertiges Wort der Sprache aussehen soll, sondern formuliert Regeln, nach denen Wörter schrittweise gebildet werden. |
|
Reguläre Sprachen
Reguläre Sprachen sind einfach aufgebaut, es gibt aber viele Anwendungen dafür. Insbesondere sind es genau die Sprachen, die man mit einem endlichen Automaten überprüfen kann. Hier geht es auch um Verfahren, wie man zu einem endlichen Automaten eine passende Grammatik bestimmt und umgekehrt zu einer vorgegebenen regulären Sprache einen endlichen Automaten, der diese Sprache akzeptiert. |
|
Kontextfreie Sprachen
Kontextfreie Sprachen sind eine Erweiterung der regulären Sprachen. Es gibt mehr Möglichkeiten, Produktionen zu bilden. Für die Überprüfung einer kontextfreien Sprache, die nicht regulär ist, braucht man einen Kellerautomaten. Mit der Einteilung der formalen Sprachen nach Chomsky wird das Kapitel "Formale Sprachen" abgerundet. |