Introduction to Formal Language Theory
Course Description: The course provides an introduction to the theory of formal languages, grammars and automatons 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.
At the end of the course the participants will know the fundamental concepts of formal language theory, the central results and the basic proof techniques. They will gain the necessary methods to dive deeper into the subject by self-study. The course offers supplementary learning modules, such as short quizzes, take-home exercises and audio-visual material.
Day 1 Modeling natural languages as formal languages
Day 2 Formal grammars and the Chomsky hierarchy
Day 3 Regular and context-free languages: automatons and closure properties
Day 4 + Day 5 Context-sensitive and recursive enumerable languages
Schedule of all courses