Formal Languages in Theory and Practice
ESSLLI 2019 course
week 2, 11:00 – 12:30
Central concepts in theoretical linguistics like “phrase structure” are derived from formal language theory. A theory that at the same time provides the theoretical foundations of computation. The course introduces formal languages, grammars and automatons and discusses the question of the structural complexity of natural languages.
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.
Hopcroft, John E., Rajeev Motwani and Jeffrey D. Ullmann. 2006. Introduction to Automata Theory, Languages, and Computation. 3rd Edition. Addison-Wesley.
Partee, Barbara H., Alice ter Meulen and Robert E. Wall. 1990. Mathematical Methods in Linguistics. Kluwer Academic Publishers.
Müller, Stefan. 2016. Grammatical theory. From transformational grammar to constraint-based approaches. Language Science Press.
Shieber, Stuart M. 1985. Evidence against the context-freeness of natural language. Linguistics and Philosophy 8. 333-343.
Pullum, Geoffrey K. and Gerald Gazdar. 1982. Natural Languages and Context-Free Languages. Linguistics and Philosophy Vol. 4, No. 4. 471-504.
Gazdar, Gerald and Geoffrey K. Pullum. 1985. Computationally relevant properties of natural languages and their grammars. New Generation Computing 3. 273–306.
Pullum, Geoffrey K. 1986. Footloose and context-free. Natural Language and Linguistic Theory 4. 409–414.
Pullum, Geoffrey K. 1987. Nobody goes around at LSA meetings offering odds. Natural Language and Linguistic Theory 5. 303–309.