Formal Languages in Theory and Practice

Kata Balogh (Heinrich-Heine-Universität Düsseldorfand, Germany) and Wiebke Petersen (Heinrich-Heine-Universität Düsseldorfand, Germany)

The course provides an introduction to the theory of formal languages for participants with no or little prior knowledge of formal systems. It concentrates on the question of “How complex are natural languages?” and introduces formal languages from a linguistic point of view. The following topics will be covered by the course: modeling natural languages as formal languages, the Chomsky hierarchy and the properties of its language classes, grammars and automatons for language generation and acceptance, and decision problems and the notion of reducibility. Next to the theoretical introduction, we will also provide (simple) implementations in Prolog.