CSE477-Ling549: Mathematical Techniques in Linguistics, Fall 2008
If you are registered for this course in Fall 08 please click
here each time you visit this homepage. You will find
here some notes, hints to some problems, assignments, and other useful
Class: Tue 6 p.m. Towne 309
Office Hours: By appointment
This course will deal with basic techniques in mathematical linguistics,
especially focusing on grammars, formal languages, automata, role of formal
grammars and machines in linguistics (in phonology, morphology, syntax,
semantics, and even some aspects of discourse).
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
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
Elements of the Theory of Computation, H.R. Lewis and C.H. Papadimitriou,
Prentice Hall, 1997.
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.
You should do all the assigned reading.
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.
This us a tentative schedule. It will be adjusted as we go along depending the speed with which I can cover the material due to the almost bi-modal distribution of the backgrounds of the students in the class. It will also depend on some additional topics we might do during the term.
Another factor that will affect the schedule is the convenience of some outside speakers if I am able to arrange the visits.
- (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,
- (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.
Last updated on September 4 2008