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.

MW 9--10:15 AM in MMH 3418

Ewan Dunbar
MMH1413E

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

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

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

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:

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.

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)
	return(final)
}

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.

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.

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.

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.

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.