Formal Language Theory for Natural Language Processing

Shuly Wintner
Section: Computation
Level: Foudational


This course is a mild introduction to Formal Language Theory for students with little or no background in formal systems. The motivation is Natural Language Processing, and the presentation is geared towards NLP applications, with extensive linguistically motivated examples. Still, mathematical rigor is not compromised, and students are expected to have a formal grasp of the material by the end of the course.

The topics to be covered include: set theory; regular languages and regular expressions; languages vs. computational machinery; finite state automata; finite state transducers; context free grammars and languages; the Chomsky hierarchy; weak and strong generative capacity; and grammar equivalence.


PDFlecture notes


Shuly Wintner
Department of Computer Science, University of Haifa
31905 Haifa, Israel
Phone: +972 (4) 8240259
Fax: +972 (4) 8249331