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 2021
Time T-R 4-5:20pm
Location Eads 102
Office January 206 / Zoom
Office Hours W 1-2pm


All class sessions are conducted in person, and attendance is required. This may change as the world sees fit. As this class is primarily seminar-style discussion, sessions will not be recorded by default. However, always prioritze your own health and the health of your peers over any academic obligations. Excused absences are unavoidable; please just keep an open line of communication.


  • 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
8/31/2021 What is Learnability? Gold 1967, Heinz 2016
9/7/2021 The Chomsky Hierarchy Tesar 2012, Partee et al 1990, Heinz & Idsardi 2012
9/14/2021 The Subregular Hierarchy Rogers & Pullum 2011, Rogers et al. 2013, Heinz 2010, Partee et al 1990
9/28/2021 Phonology and regular relations Kaplan & Kay 1994, Karttunen & Beesley 2005, Gildea & Jurafsky 1996
10/12/2021 Formal characterization of natural language syntax Shieber 1985, Pullum & Gazdar 1982, Karlsson 2007, Partee et al 1990, Chomsky 1957
10/21/2021 Learning syntactic patterns Clark & Eyraud 2007, Clark 2017
10/28/2021 Beyond formal languages: parallel distributed processing Rumelhart & McClelland 1985, Pinker & Prince 1988, Pater 2019
11/9/2021 Constraint-based parallelism Tesar & Prince 2003, Prince & Tesar 2006, Tesar 1995, Zsiga 2013
11/23/2021 Advanced learning algorithms for OT Hayes & Wilson 2008, Boersma & Hayes 2001, Nyman & Tesar 2019
11/30/2021 Presentations  

COVID-19 Health and Safety Protocols

Exceptions to course attendance policies, expectations, and requirements because of a COVID-19 diagnosis, symptoms consistent with COVID-19, or exposure to a person with a confirmed or suspected COVID-19 diagnosis that requires quarantine or isolation will be made in collaboration between the student and instructor. In these cases, please notify your instructor as soon as possible to discuss appropriate accommodations.

While on campus, it is imperative that students follow all public health guidelines established to reduce the risk of COVID-19 transmission within our community. The full set of University protocols can be found at This includes:

  • Completing a self-screening using the WashU COVID-19 Screening app every day before coming to campus or leaving your residence hall room. If you do not receive a green check and pass the screening, you are not permitted to come to campus or leave your residence hall room. You must contact the COVID Call Center (314-362-5056) or the Habif Health and Wellness Center (314 935-6666) immediately. Note: In addition to the symptoms listed in the screening tool, everyone also should pay attention to symptoms that are new or different for you, including things like headache and congestion, particularly in combination with diarrhea. These can also be signs of COVID-19. Call the COVID Call Center or Habif to report these symptoms.
  • Complying with universal masking. All individuals on campus must wear disposable masks or cloth face coverings while occupying indoor public settings, including: multi-person offices, hallways, stairwells, elevators, meeting rooms, classrooms and restrooms. Masks are encouraged but not required for outdoor activities, particularly at large events or in crowded settings. Students with disabilities for whom masked instructors or classmates create a communication barrier are encouraged to contact Disability Resources () or talk to their instructor for assistance in determining reasonable adjustments. Adjustments may involve amplification devices, captioning, or clear masks but will not allow for the disregard of mask policies.
  • Maintaining physical distancing as needed. While distancing requirements have been removed for vaccinated students, those who are not fully vaccinated are strongly encouraged, for their own health, to maintain a distance of 6 ft from others in the classroom. If you are not able to be vaccinated or have conditions that may put you at increased risk of failed immunity and classroom activities would bring you in frequent proximity to other students, contact your instructor to discuss alternatives.
  • Practicing healthy personal hygiene, including frequent handwashing with soap and warm water for at least 20 seconds and/or using hand sanitizer with at least 60% alcohol.

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