After a brief introduction to the basic concepts of set theory, relations, and functions, and properties of relations, we will cover the following topics, not all at the same level.

Grammars, languages, and automata- finite state grammars, regular expressions, finite state transducers, context-free grammars and pushdown automata. Context-sensitive grammars- string context sensitivity and structural context-sensitivity. Mildly context-sensitive grammars. Turing machines. Grammars as deductive systems, parsing as deduction. Stochastic grammars.

The course will deal with these topics in a very basic and introductory manner, i.e., the key ideas of the proofs and not detailed proofs will be presented. More importantly, throughout the course plenty of linguistic examples will be discussed to bring out the linguistic relevance of these topics.

There are other textbooks on Formal Languages and Automata. I will bring some of these books to the class for you to look at. You may already own a text book in this area, perhaps the one by Michael Sipser.

Anyone of these books would be fine. I do not want you to buy another book if you already have one. If you do not have any book on this topic then I recommend the book mentioned in the first paragraph. My notes will be self contained and I will follow a consistent notation. Different books have their own notations but it is easy to switch the notation, once you understand the key ideas.

A book you may also wish to consult:

Mathematical Methods in Linguistics, Barbara Partee, Alice ter Meulen, and Robert Wall, North Holland, 1994.

I will do some problems in the class and will assign some for homework. I expect you do the assigned reading ahead of time so that we can move on rapidly

I expect you to do some additional reading. For example, those with linguistics background but no computer science background should do some extra reading and/or do some extra problems. Those in cse with no linguistics background should do some reading from one of the introductory book in linguistics. Please discuss your additional reading with me individually.

There will be two exams--mid-term and final. Both will be closed book exams.

Another factor that will affect the schedule is the convenience of some outside speakers if I am able to arrange the visits.

n- (9/9)
**General introduction and intro to finite state automata** - (9/16)
**A quick review basic concepts (Chapter 1)**: mainly to answer questions and continue finite state automata (Chapter 2). - (9/23/- 9/30)
**Finite state automata**: State diagrams, deterministic and nondeterministic fsa, regular expressions and languages, type 3 or finite state grammars, linguistic applications. See a set of slides covering finite sate grammars/automata, context-free grammars, pushdown automata, etc.comprehensive-slides. Begin with finite state transducers (not from the textbook) with applications. For an early application of fst for parsing see Uniparse - (10/7, 10/14)
**Context-free grammars**: pushdown automata, pumping lemma, linguistic applications. (Chapter 3). - (10/21, 10/28)
**Strong generative capacity**: Structural descriptions, beyond context-free grammars, mildly context-sensitive grammars, types of context-sensitivity, tree-adjoining grammars, categorial grammars. applications to linguistics. (not from the textbook) - (11/4, 11/11) For an introduction to
**lexicalized tree-adjoining grammars**, see LTAG. This is a long paper. Sections 1 through 8 are directly relevant (pages 1-34). Skip Sections 9 and 10. A general introduction is also provided in a set of slides, see Slides-General-Intro. For LTAG slides**LTAG-slides**, see LTAG-slides. - (11/18, 11/25)
**Categorial Grammars**, for a brief introduction, see Intro-CG. - (12/2)
**Turing machines**: A fast treatment of Turing machines, linguistic relevance, other relevant topics.**Some advanced topics**: Linguistic and psycholinguistic relevance, further discussion of the relationship of grammars and machines, parsing,

The above schedule is quite ambitious. It will no doubt slip. Anyway, let us see how it goes. I will make some adjustments as we go along.

- 95-final
- 96-midterm
- 96-final
- 97-midterm
- 97-final
- cse477-ling549-Fall98-Final-Exam
- 99-midterm
- 99-final
- 00-midterm
- 00-final
- 02-midterm
- 02-final.pdf
- 02-final.pdf
- 03-midterm.pdf
- 03-final.pdf
- tag-tutorial
- xtag-project: information about the xtag project, access to more tutorial slides
- mol: ACL Special Interest Group in Mathematics of Language (MOL)

Last updated on September 4 2008