CSE477-Ling549: Mathematical Techniques in Linguistics, Fall 2009

If you are registered for this course in Fall 09 please click here each time you visit this homepage. You will find here some notes, hints to some problems, assignments, and other useful information.

Instructor: Aravind K. Joshi ( joshi@seas.upenn.edu)

Class: Tue 6 p.m. Towne 309

Office Hours: By appointment

Introduction

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

Textbook

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.

What you need to do

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.

Tentative Schedule

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.

n

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.

Other Useful Information

Last updated on September 8 2009