CS4114 - Formal Languages
Spring 2008, CRN 11772
MW 4:00pm, Pamplin 3010

Class Materials URL: http://pixel.cs.vt.edu/courses/cs4114.html

Instructors

R.W. Ehrich, KW2 129, Office Hours: M, W 2:45 - 3:45 in McB 636, or by appointment (1-5420)

Yang Pu, Office Hours: Tu, Th 1:45 - 3:45 in McB 133, or by appointment

Objectives

Formal languages and the relation between certain classes of languages and classes of automata is one of the essential theoretical foundations of computer science. This has direct application, not only to programming languages, but to the art of programming itself. The central theme is the discussion of four classes of language models and generative and analytical mechanisms for those classes. The course is primarily theoretical and is based heavily on mathematical notational systems.

Grading

The semester grade will be based upon assignments issued in class (50%), one midterm (20%), and a comprehensive final examination (30%). 25% credit per day will be deducted from late homework.

Homework

Homework assignments will be posted on the class web page and will be due by 5pm on the assigned dates. NO LATE HOMEWORK WILL BE ACCEPTED unless by prior approval. All homework solutions must be legible, well-reasoned, and accurately expressed. All work submitted for a grade must be the student's own work. If you have a question about the grading of an assignment or an exam, you should speak with your GTA within a week after the assignment is returned.

Exams

Midterm, Wednesday, February 20
Final, Tuesday, May 6, 3:25pm - (NOTE: Classes end Wednesday, April 30)

No missed exams will be accepted unless by prior approval. All exams are closed-book exams. The final covers all the material in the course.

Ethics

The Honor Code will be strictly enforced. It is a violation to represent joint work as your own or to let others use your work; always acknowledge any assistance you received in preparing work that bears your name. You are expected to work independently unless explicitly permitted to collaborate on a particular assignment. It is not a violation to discuss approaches to problems with others; however, it IS a violation to use wording or expressions in your assignments that have been written by others without acknowledging the source.

Reading

Reading assignments accompany the lecture material and will be issued in class. The reading material requires a serious effort and is important to learning the course material. Also on reserve in the library are several classical papers on formal languages. These will be assigned as appropriate to the lecture material.

Prerequisites

Math 3134 or Math 3034 and fluency in mathematical expression.

Text

Sudkamp, Thomas A., Languages and Machines, 3rd Edition, Addison Wesley, 2006.

Lecture Notes (Optional)

Formal Languages & Automata Theory, A-1 Copies, University Mall.

References (2 compilations on reserve at the Library)

Chomsky, N., "On Certain Formal Properties of Grammars, Information and Control(2), 1959, pp. 137-167.
Kuroda,, S. Y., "Classes of Languages and Linear Bounded Automata," Information and Control(7), 1964, pp. 207-223.
Landweber, P. S., "Three Theorems on Phrase Structure Grammars of Type 1," Information and Control(6), 1963, pp. 131-136.
Landweber, P. S., "Decision Problems of Phrase Structure Grammars," IEEE Transactions on Electronic Computers(13), 1964, pp. 354-362.
Naur, P., et al., "Revised Report on the Algorithmic Language ALGOL 60", CACM(6) No. 1, January 1963, pp. 1-17.
Rabin, M. O., and Scott, D., "Finite Automata and Their Decision Problems," IBM J. Research and Dev.(3), 1959, pp. 114-125.

Course Outline

Mathematical foundations

10%

Relations, functions, cardinality, recursive definitions, proof techniques

Languages and grammars

30%

Foundations of language theory, string generation, sets

Regular languages and expressions

Formal languages and grammars

Context free grammars

Derivations and derivation trees

Languages from grammars

Grammars from languages

Regular grammars

Regular expressions from regular grammars

Regular grammars from regular expressions

Equality and properties of languages

Programming language syntax: BNF and Algol 60 specification

Ambiguity and inherent ambiguity

Normal forms

Deterministic parsing and search

10%

Breadth-First, Top-Down

Depth-First, Top-Down

Breadth-First, Bottom-Up

Depth-First, Bottom-Up

Finite automata

20%

Deterministic finite automata

Representations

Acceptors

Properties of DFA languages

Nondeterministic finite automata

Acceptors

Properties of NFA languages

Removing nondeterminism

Equivalence of regular languages, NFAs, and regular expressions

Proving regularity or non-regularity of languages (Pumping Lemma)

Minimization of DFAs

Closure properties of regular languages

Pushdown automata

15%

Acceptance

Context free grammars to PDAs

PDAs to context free grammars

Pumping Lemma

Closure properties

Turing machines

10%

Acceptance

Equivalent models

Church’s Thesis

Undecidability of the Halting Problem

Decidable and undecidable problems

Chomsky hierarchy

CS4114 - Formal Languages Spring 2008, CRN 11772 MW 4:00pm, Pamplin 3010