Formal Languages

Formal languages are an essential instrument of the theoretical computer science to formalise problem statements. They enable a structured and linearized representation of data. Applications in practice can be found, for example, in compiler construction. Known examples of formal languages that occur in practice are programming languages or HTML and XML.

The concept of formal language is very general. Important subclasses are regular and context-free languages, which also play a major role in parsing.

We are interested in Formal Languages in connection with Circuit Complexity. Subclasses of regular languages play an important role.