Ling 427 Learnability and Computation in Linguistic Theory

Dr. Nick Danis,
Washington University in St. Louis


“This course introduces the advanced linguistics or computer science student to the fields of learnability and computation as they apply to the study of linguistic theories and natural language. Topics covered include the formal language hierarchy, including the subregular languages; issues in the learnability of phonology, morphology, and syntax; and algorithms specific to constraint-based linguistic grammars. Prerequisites: either CS 131 or Ling 317 and at least one of the following: Ling 309, Ling 311, Ling 313, or Ling 315.”

Course Info

Course Number L44 Ling 427
Semester Fall 2022
Time 4:00-5:20pm
Location Eads 112
Office January 206
Office Hours TBD


  • Explore the relationship between natural language and the formal language hierarchy
  • Critically examine the comparison of theories from a computational point of view
  • Implement and understand various algorithms defined for linguistic theories in a hands-on way

Required Materials

All readings are posted as PDFs on Canvas. Occasionally, the use of software on the students’ own computers is necessary, but this software is free and cross-platform. More details will be given in class.


Your grade breakdown is shown below.

Item pct
Assignments 20%
Participation & Discussions 30%
Papers 50%


There will be occasional short problem sets on the logic and formalisms discussed in class. Depending on your background, these might be review or they might be new. The purpose of these assignments is to make sure everyone is on the same page.

Participation and Discussions

There will be multiple student-led discussion days throughout the semester. Your discussion group will have to prepare a handout to guide the rest of the class through that day’s reading. Further details are on Canvas.


There is both a midterm squib (~5 pages) and a final paper (10 pages). Both involve application of course concepts to natural language data, with the freedom to incorporate any expertise you may have.

As part of the final paper, there will also be a proposal stage and a presentation during the last weeks of class. You should start thinking about topics now, and feel free to reach out with any ideas or questions.

Letter grades

Letter grades are assigned based off the following scale. Numerical grades are not rounded.

  • 100 ≥ A+ ≥ 98
  • 98 > A ≥ 93
  • 93 > A- ≥ 90
  • 90 > B+ ≥ 87
  • 87 > B ≥ 83
  • 83 > B- ≥ 80
  • 80 > C+ ≥ 77
  • 77 > C ≥ 73
  • 73 > C- ≥ 70
  • 70 > D+ ≥ 67
  • 67 > D ≥ 63
  • 63 > D- ≥ 60

If you are taking this class pass/fail, you must receive at least a C- (70%) to pass.

If you believe there has been an error in grading, I am happy to discuss it with you. However, you must bring it up to me within one week of the graded assignment being returned to you. After this, the grade is considered final.


The exact schedule is likely to change as the semester progresses. Please see Canvas for all up-to-date readings and assignment due dates.

Date Unit Readings
Week 1 What is Learnability? Gold 1967, Heinz 2016
Week 2 The Chomsky Hierarchy Tesar 2012, Partee et al 1990, Heinz & Idsardi 2012
Week 3-4 The Subregular Hierarchy Rogers & Pullum 2011, Rogers et al. 2013, Heinz 2010, Partee et al 1990
Week 5-6 Phonology and regular relations Kaplan & Kay 1994, Karttunen & Beesley 2005, Gildea & Jurafsky 1996
Week 7-8 Formal characterization of natural language syntax Shieber 1985, Pullum & Gazdar 1982, Karlsson 2007, Partee et al 1990, Chomsky 1957
Week 9 Learning syntactic patterns Clark & Eyraud 2007, Clark 2017
Week 10 Beyond formal languages: parallel distributed processing Rumelhart & McClelland 1985, Pinker & Prince 1988, Pater 2019
Week 11-12 Constraint-based parallelism Tesar & Prince 2003, Prince & Tesar 2006, Tesar 1995, Zsiga 2013
Week 13 Advanced learning algorithms for OT Hayes & Wilson 2008, Boersma & Hayes 2001, Nyman & Tesar 2019
Week Presentations  

Academic Integrity

This course adheres to the university’s Academic Integrity Policy, and takes cheating and plagiarism very seriously. All work completed online must be done alone unless instructed otherwise, and no resources not approved by the instructor may be used during exams.

ADA Compliance

Washington University is committed to providing accommodations and/or services to students with documented disabilities. Students who are seeking support for a disability or a suspected disability should contact Disability Resources at 935-4153. Disability Resources is responsible for approving all disability-related accommodations for WU students, and students are responsible for providing faculty members with formal documentation of their approved accommodations at least two weeks prior to using those accommodations. I will accept Disability Resources VISA forms by email and personal delivery. If you have already been approved for accommodations, I request that you provide me with a copy of your VISA within the first two weeks of the semester. Please see more information at

Sexual Assault Resources

The University is committed to offering reasonable academic accommodations (e.g., no contact order, course changes) to students who are victims of relationship or sexual violence, regardless of whether they seek criminal or disciplinary action. If you need to request such accommodations, please contact the Relationship and Sexual Violence Prevention Center (RSVP) at or 314-935-3445 to schedule an appointment with an RSVP confidential, licensed counselor. Information shared with counselors is confidential. However, requests for accommodations will be coordinated with the appropriate University administrators and faculty. Please see more information at