Formale Sprachen

Formale Sprachen sind ein grundlegendes Mittel der theoretischen Informatik um Problemstellungen zu Formalisieren. Sie ermöglichen eine strukturierte und linearisierte Darstellung von Daten. Anwendungen in der Praxis sind beispielweise im Compilerbau zu finden. Bekannte Beispiele für Formale Sprachen, die in der Praxis auftauchen, sind Programmiersprachen, oder auch HTML und XML.

Der Begriff der formalen Sprache ist sehr allgemein gefasst. Wichtige Unterklassen sind die regulären und kontextfreien Sprachen, welche auch beim Parsing eine große Rolle spielen.

Wir interessieren uns für Formale Sprachen sehr stark im Zusammenhang mit der Circuit Complexity. Dabei spielen Unterklassen von regulären Sprachen eine wichtige Rolle.