LING 106: Introduction to Formal Linguistics

Instructor: Lance Nathan
613 Williams Hall
nathanla@ling.upenn.edu
Office Hours: Wednesday, 3pm to 5pm

TA: Satoshi Nambu
401 Williams Hall
satoshin@ling.upenn.edu
Office Hours: TBA


The syllabus in PDF format (also handed out on the first day of class)

Course Description

The goal of this course is to define certain formal properties that underlie the architecture of language. To this end, mathematical tools are provided that help us understand and classify the complex structures and rules that constitute language and grammar. These tools include set theory, propositional logic, information theory, formal language theory, automata theory, as well as a brief introduction to the semantics of natural language.

Readings and Texts

Textbook: None.

Other texts: To be distributed as necessary.

Requirements and Grade

Homework assignments (weekly): 60% (total)
Homework assignments must be in Catherine's possession by the end of class (2:00 pm) on the due date.

Midterm and final exams: 30%

Attendance and class participation: 10%

Violations of academic integrity will be taken seriously!
It is your responsibility to understand the University's policy.
See your Class Handbook, the university's website, etc.

Organization and Outline of the Course

Mathematical background
I. Isolating linguistic units
  • Lexical Analysis 1
  • Lexical Analysis 2 - The Lexicon
  • Ciphers
  • Linear B
II. Syntax (and Phonology): building strings of units
  • Syntax: Combining Words into Sentences
  • Syntax: (Deterministic) Finite-State Automata
  • Non-Deterministic Finite-State Automata
  • The Pumping Lemma
  • Beyond Regular Grammars
  • Phonology and finite state transducers
  • The Right Way to Do Syntax
III. Semantics: interpreting the meaning of strings of units
  • Propositional Logic
  • Predicate Logic
  • More Predicate Logic