Home » ESSLLI 2019 course

Contact

Address:
Department of Computational Linguistics
Heinrich-Heine-Universität Düsseldorf
Universitätsstr. 1
D-40225 Düsseldorf, Germany

Email:
balogh {AT} ling.hhu.de

Telephone:
+49 211 81-12554 (secretary)

Privacy / Datenschutzerklärung

ESSLLI 2019 course

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.

Lecturers
Wiebke Petersen
Kata Balogh
(Heinrich-Heine-Universität Düsseldorf)

Slides
Day 0: basic set theory (reminder)
Day 1: SLIDES
Day 2: SLIDES, JFLAP, Exorciser
Day 3: SLIDES
Day 4: SLIDES, HANDOUT version, Turing machine simulator
Day 5: SLIDES
COURSE SUMMARY

Literature
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.