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 910:15 AM in MMH 3418
Instructor
Ewan Dunbar
MMH1413E
Office Hours
Tu 12 PM, W 10:1511: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, neighborhooddistinct languages, local and piecewise type automata, stress systems, phonotactics, phonological processes, rulebased phonology, Optimality Theory. Topics which may be covered: contextfree grammars, mildly contextsensitive grammars, weighted finitestate transducers, learnability.
Prerequisites
Permission of instructor.
Materials
Schedule
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.21.4, Linz, ch. 1, sec. 1.1

Formal languages

M Jan 30


Syntactic Structures pp. 1125, 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. 12

Syntax

M Feb 20

Homefun 2 (FSAs/RLs)


Stress

W Feb 22


Kenstowicz, ch. 10, sec. 10.110.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)


Neighborhooddistinct languages

M Mar 12



Neighborhooddistinct 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 neighborhooddistinctness

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



Finitestate 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

FrankSatta 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 (contextfree grammars and mildly contextsensitive grammars); weighted finitestate 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
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







…

You will need to submit a proposal part way through the semester. This is a onepage summary explaining the problem to be solved and why you think you have something useful to say about it.
Evaluation
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
90100%

A

8089%

B

7079%

C

6069%

D

059%

F

Submissions
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)
return(final)
}
Resubmissions
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 regraded. 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 regraded.
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.