
LING 106: INTRODUCTION TO FORMAL LINGUISTICS
COURSE DESCRIPTION
Prerequisites: None.
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.
Basic outline of the course:
(0. Review of Set Theory.)
 I. Isolating linguistic units.
 Distributional analysis.
 Application to ciphers. Deciphering Linear B.
 II. Syntax: building strings of units.
 Regular languages.
 Pumping lemma in regular languages.
 Context free grammars.
 Pumping lemma in context free grammars.
 Categorial Grammars.
 III. Semantics: interpreting the meaning of
strings of units.
 Review of Propositional Logic.
 Brief introduction to compositional semantics.
REQUIREMENTS
Class and recitation attendance. 

Readings: lecture notes and
assigned readings. There is no textbook. 

Homework assignments
(approx. 89): 
80% 
Late homework will not be
accepted. 

Two quizzes: 
20% 
See your Class of 200x Handbook for University policy on academic integrity.
BACKGROUND READINGS
They will be distributed in class (or available at van Pelt).
LECTURE NOTES AND HOMEWORK ASSIGNMENTS
Materials will appear posted as the course progresses.
 Topic 0: Review of Set Theory.
 Topics 1 and 2: Distributional Analysis.
Application to ciphers. Deciphering Linear B.
 Topics 3 and 4: Regular Languages. Pumping Lemma
in Regular Languages.
 Topic 5 and 6: Beyond Finite State Automata.
 Topic 8 and 9: Semantics: interpreting the
meaning of strings of units.
