Discrete Mathematical Models of Mental Grammar
LING499B Spring 2012

This is the course webpage and the course syllabus. This page is available as a PDF here.

Meeting information

MW 9--10:15 AM in MMH 3418


Ewan Dunbar

Office Hours

Tu 1--2 PM, W 10:15--11:15 AM

Course description

This course will examine the mathematical principles underlying grammars in human language, with a focus on phonology. This course aims to give students an understanding of the fundamental computational differences between phonological and syntactic cognition and bring students up to date with recent research in mathematical linguistics. The focus of this course is on understanding human language cognition, but it will also be of use to students with an interest in natural language processing. This is a mathematically intensive course, and students must feel very comfortable doing mathematical proofs using elementary set theory, combinatorics, and induction. Students must contact the instructor to assess appropriateness of the course before registering. Topics: regular languages, finite state automata, Turing machines, finite state transducers, neighborhood-distinct languages, local and piecewise type automata, stress systems, phonotactics, phonological processes, rule-based phonology, Optimality Theory. Topics which may be covered: context-free grammars, mildly context-sensitive grammars, weighted finite-state transducers, learnability.


Permission of instructor.


Readings posted here (password protected); see below for links to readings for specific days


Readings listed are expected to be read before class, except for the ones listed under the first class (those are preparation for the first homefun).
Date Assignment due Readings Topic
W Jan 25 Hopcroft et al., ch. 1, sec. 1.2--1.4, Linz, ch. 1, sec. 1.1 Formal languages
M Jan 30 Syntactic Structures pp. 11--25, Hopcroft et al., ch. 1 sec. 1.5, Hopcroft et al., ch. 2 sec. 2.2 Syntax/FSAs
W Feb 01 Homefun 1 (FLs, proof techniques) Hopcroft et al., ch. 4 sec. 4.1 FSAs/RLs
M Feb 06 Hopcroft et al., ch. 2 sec. 2.3 FSAs/RLs
W Feb 08 Hopcroft et al., ch. 4 sec. 4.4, sec 4.2 FSAs/RLs
M Feb 13 Hopcroft et al., ch. 4 sec. 4.2 FSAs/RLs
W Feb 15 Chomsky 1956, sec. 1--2 Syntax
M Feb 20 Homefun 2 (FSAs/RLs) Stress
W Feb 22 Kenstowicz, ch. 10, sec. 10.1--10.3 Stress
M Feb 27 Stress
W Feb 29 Stress
M Mar 05 Heinz 2007, ch 2 sec 2 Stress and FSAs
W Mar 07 Homefun 3 (Stress) Neighborhood-distinct languages
M Mar 12 Neighborhood-distinct languages, Extrametricality
W Mar 14 Strictly local
M Mar 19 —Spring Break—
W Mar 21 —Spring Break—
M Mar 26 (Moved)
W Mar 28 Homefun 4 (Stress and regular lgs.) Stress and neighborhood-distinctness
M Apr 02 Intro to segmental phonology
W Apr 04 Rule ordering (Russian and Tonkawa problems)
M Apr 09 The phonological cycle (Klamath)
W Apr 11 Project proposal Harmony
M Apr 16 Finite-state transducers
W Apr 18 Kaplan and Kay 1994 Regularity of rule systems
M Apr 23 Homefun 5: Kenstowicz Exercise 5.1 (Segmental) Kaplan and Kay 1994 Regularity of rule systems
W Apr 25 Kaplan and Kay 1994 Regularity of rule systems
M Apr 30 Progress report Optimality Theory
W May 02 Frank and Satta 1998 Frank-Satta Theorem
M May 07 Homefun 6 (Transducers) Weighted Finite State Machines
W May 09 Final project Riggle 2009 Violation Semiring

We may extend the main topics of the course into the last week. In whatever time is left, we will cover one of the following three topics: syntax (context-free grammars and mildly context-sensitive grammars); weighted finite-state transducers (used in NLP); learning of FSAs and FSTs (theoretical bounds on learnability). This topic will be up to a class vote after Spring Break.

Additional readings

Formal languages basics: Linz, ch. 1, sec. 1.2
Regular expressions: Hopcroft et al., ch. 3
Myhill-Nerode theorem: Nerode 1958
Nested dependencies: Gibson and Thomas 1999, Vasishth et al. 2010
Cross-serial dependencies: Shieber 1985, Bach et al. 1986
English stress: Chomsky and Halle 1968 (Chapter 3), Liberman and Prince 1977
Cyclicity: Kenstowicz, Chapter 5
Optimality Theory: Prince and Smolensky 1993

Final project

You will be expected to do a small final project for this course and write it up. It must have the goal of advancing our (not just your) understanding of something related to the contents of this course. It should also reflect that you learned something by either (i) translating technical stuff into ideas you can explain in an insightful way or (ii) translating ideas into technical stuff in a skillful way. Some possible ideas might be:
Idea How to make it small
The types of formal devices we will learn about in this course do not cover everything we know about human language—yet! Advance our understanding of linguistics by making a specific proposal about how to cover some of those things. You would be evaluated mostly on your understanding of the data and whether it really aligns with the theory the way you say it does. You would just need to have one tiny piece of a solution that you think would convince a skeptical but friendly observer you’re on the right track.
You can use formalisms closely related to the ones we will talk about to do lots of interesting NLP tasks. Advance our understanding of some problem in NLP by finding and describing a shortcoming in a state-of-the-art system, and making some suggestions for how that might be overcome. You would be evaluated mostly on your understanding of the other system. Your idea would not need to be implemented—just an idea, possibly half-baked.
There are still other applications for the types of formalisms we will learn about. Explore a new idea for something that would be useful in a different domain. Pick a domain you already know about. You would be evaluated mostly on your explanation of how that domain lines up with the stuff we have talked about.
You will need to submit a proposal part way through the semester. This is a one-page summary explaining the problem to be solved and why you think you have something useful to say about it.


Homefun 1 15
Homefun 2 15
Homefun 3 15
Homefun 4 15
Homefun 5 15
Homefun 6 15
Project Proposal 9
Progress report 1
Final Project 15

Only the best five homefuns will count towards your grade.
On any homefun question, you may write “I DO NOT KNOW HOW TO ANSWER THIS QUESTION” and you will receive ten percent of the possible points for that question. You must write this, and only this! Writing this and a partial proposed solution—or indeed writing any two possible, conflicting answers without explanation—will result in an automatic zero for the question.

Letter grades

90--100% A
80--89% B
70--79% C
60--69% D
0--59% F


Assignments should be submitted (to me) by email, on paper, or in any other readable format, but, in either case, if I am not physically present in the room when you submit it, you will need to make sure that I have received it and can read it! Assignments must be submitted by 9:05AM on the day they are listed as due.

Late policy

Assignments submitted after the beginning of class will be subject to a late penalty. Here is the R code I will use for computing the late penalty and a plot of the penalty as a function of time:
# Return value: actual grade
# t: time in hours since the beginning of class
# m: total available grade for the assignment
# g: grade that you would have been assigned for the assignment
#    if it had not been late
penalized_grade <- function(t, m, g) {
	rate <- 0.0216
	penalty <- rate^(0.5)*(exp(rate*t)-1)
	final <- max(0, g - m*penalty)
figure penalized_grade.png


After it is graded, any assignment may be resubmitted for extra points up to seven days after it is returned. The original assignment should be submitted, along with a corrected version of any questions that are meant to be re-graded. The maximum new grade is [old grade + 0.75⋅(m − old grade)], where m is the total available grade, as above. This can only be done once (i.e., resubmissions may not be resubmitted). No late resubmissions will be re-graded.

Religious holidays, excused absences, and cancellations

Under normal circumstances, lecture is your only chance to hear something for the first time; if you miss class, I will expect you to read the lecture notes and supplementary materials thoroughly before coming with questions. Exceptional circumstances include: religious holidays; medical absences; family emergencies; etc. Under these circumstances, do not hesitate to arrange for another time to go over the lecture notes together. The due date for assignments will also be shifted accordingly, if appropriate documentation is provided. If class needs to be cancelled, arrangements will be made for a makeup class.

Policy on collaboration

Your work should be your own. You should not give or receive any information about part of a solution to a problem unless you and the other party both firmly and honestly believe you have a working solution. If, after coming to a solution, you find a flaw because of someone else’s input, write up your original answer and a detailed correction based on this new information. In addition to detailing how the correct solution differs from yours, also explain what error led you to the incorrect solution and where you found the correct one. It is possible to receive full points for such an “incremental” solution. Failure to provide your original answer or the source of your information in this case, will count as academic dishonesty.

Academic dishonesty

I follow the University’s policies on academic honesty and penalize cheating, fabrication, plagiarism, and facilitation of academic dishonesty. Cheating is intentionally using or attempting to use unauthorized materials, information, or study aids in any academic exercise. Fabrication is intentional and unauthorized falsification or invention of any information or citation in an academic exercise. Plagiarism is intentionally or knowingly representing the words or ideas of another as one’s own in any academic exercise. Facilitating academic dishonesty is intentionally or knowingly helping or attempting to help another to cheat, fabricate, plagiarize, or facilitate academic dishonesty. Any member of the University community who has witnessed an apparent act of academic dishonesty, or has information that reasonably leads to the conclusion that such an act has occurred or has been attempted, has the responsibility to inform the Honor Council promptly in writing. The penalties for behavior assessed to be academic dishonesty range from an “XF” grade for the course and the notation “failure due to academic dishonesty” on the student’s transcript up to suspension or expulsion. Please review the full Code of Academic Integrity used by the University.

Students with disabilities

If you have a physical disability or a learning disability, please bring it to my attention at the beginning of the course, before any assignments are due. I will make all due effort to accommodate your needs.