Formal Languages and Automata

CSc 42800–Fall 2010

 The City College of CUNY
Department of Computer Science

Instructor: Nelly Fazio
Lectures: T/Th, 5:00–6:15pm, NAC 7225
Office hours: Thursdays, 2:00–3:00pm, SH-279
Email: fazio AT cs DOT ccny DOT cuny DOT edu [Put CSc42800 in Subject line]

[ Course Description | Textbook | List of Topics | Work Load & Grading | CUNY Integrity Policy | Homework | Weekly Schedule ]

Course Description

Classes of languages; their description in terms of grammars and their recognition by automata. The Chomsky hierarchy; regular, context-free, context-sensitive and recursively enumerable languages. Application to parsing and compiler construction.

Prerequisites: CSc 30400.

Course Objectives

Successful completion of this course trains students in the following directions:
  1. Articulate the relative differences between the mathematical models of computation of varying expressive power (FA, PDA, TM);
  2. Argue about the equivalence between formal grammars and automata (eg., RE vs. FA and CFG vs. PDA);
  3. Express computational problems in terms of formal languages, and classify them with respect to the type of automata that recognize them or formal grammars that generate them;
  4. Gain familiarity with the notion of non-determinism and its role in the theory of computation.

Textbook

Introduction to Automata Theory, Languages, and Computation.
J. E. Hopcroft, R. Motwani, J. D. Ullman. 3rd ed. Addison Wesley, 2007.

List of Topics (tentative)

Work Load & Grading

NOTE: There will be NO make-up or substitute exams!

The grades for the midterm and final exams will be combined as follows:

exmGrade = max(finalGrade, avg(midGrade,finalGrade))

CUNY Integrity Policy

Cheating will not be tolerated. If you cheat, you risk losing your position as a student in the department and the college. CUNY policy on academic integrity can be found here. Failure to understand and follow these rules will constitute cheating, and will be dealt with as per university guidelines.

Homework

There will be substantial homework assignments aimed at reinforcing the material covered in class.

Late Assignment Policy: Homework are due at the beginning of the class on the due date. Late assignment will not be accepted.

Weekly Schedule

Lecture Date Topic Readings
1 Aug 26 Computation and Automata Theory. Strings, alphabets, languages. Notations and basic operations. Example of languages.
Automata and grammars. Chomsky hierarchy. Definition of different grammars and their relations.		 Ch. 1
2–3 Aug 31
5:00–7:30pm		 Double slot to make-up class of Sep 2
DFAs. NFAs. Application to text searching.		 Sec. 2.1–2.3 (except 2.3.5–2.3.6),
Sec. 2.4.1–2.4.2
  Sep 2 No class. Make-up class on Aug 31, 6:15–7:30pm, Room NAC ??.  
4 Sep 7 Equivalence of DFA and NFA. A bad case for the subset construction. DFA to recognize set of keywords. Sec 2.3.5–2.3.6,
Sec. 2.4.3
Sep 9 No class.  
  Sep 14 No class. Friday schedule  
5 Sep 16 Finite automata with ε-transitions. ε-closures. Equivalence of ε-NFA and DFA. Sec. 2.5
Sep 21 No class. Make-up class on Oct. 5, 6:15–7:30pm, Room HR 11  
Sep 23 No class. Make-up class on Oct. 7, 6:15–7:30pm, Room HR 11.  
6 Sep 28 HW1 is due today!
Regular expressions and languages. From finite automata to regular expressions.
Converting DFA's to RE's by eliminating states. 		Sec. 3.1, Sec. 3.2.1-3.2.2
7 Sep 30 From regular expressions to automata. Applications of RE's. Algebraic laws for RE. Sec. 3.2.3. Sec. 3.3-3.4
8–9 Oct 5
 Double slot to make-up class of Sep 21.
The pumping lemma for regular languages. Examples.		 Sec. 4.1
10–11 Oct 7
5:00–7:30pm		 Double slot to make-up class of Sep 23.
Closure properties of regular languages.		 Sec. 4.2
12 Oct 12 Decision properties of regular languages. Sec. 4.3
13 Oct 14 Equivalence and minimization of automata. The Myhill-Nerode Theorem. Sec. 4.4
14 Oct 19 Context-free grammars (CFG). Parse trees. Sec. 5.1-5.2
15 Oct 21 Applications of CFGs. Sec. 5.3
16 Oct 26 HW2 is due today!
Review Session.		  
17 Oct 28 Midterm Exam  
18 Nov 2 Ambiguous and non-ambiguous grammar. Inherently ambiguous languages.
Pushdown automata (PDA). Examples. 		Sec. 5.4. Sec. 6.1
19 Nov 4 Instantaneous description of a PDA. Acceptance by final state and by empty stack. Sec. 6.1.4, Sec. 6.2.1-6.2.2
20 Nov 9 Equivalence of acceptance by final state and by empty stack. Examples.
Discussion of the midterm		 Sec. 6.2.3-6.2.4
Nov 11 No class. Make-up class on Nov. 23, 6:15–7:30pm, Room ???.  
21 Nov 16 Equivalence of PDA's and CFG's Sec 6.3
22 Nov 18 Deterministic PDA.
Normal forms for CFG's: Eliminating useless symbols		 Sec. 6.4
Sec 7.1, 7.1.1-7.1.2
23–24 Nov 23
5:00–7:30pm		 Double slot to make-up class of Nov. 11.
Eliminating ε and unit productions. Chomsky Normal Form.
The pumping lemma for context-free languages. Examples.
Closure and decision properties of context-free languages. 		Sec. 7.1.3–7.1.5
Sec. 7.2, 7.3, 7.4
  Nov 25 No class! Thanksgiving!  
25 Nov 30 HW3 is due today!
Context-sensitive grammars and languages. Examples. Linear Bounded Automata (LBA). Closure properties of CSLs. 		 
26 Dec 2 Turing machines (TM) and recursive enumerable (RE) languages. Sec 8.2
27 Dec 7 Programming techniques for TM: storage in state and multi tracks.
Extensions to TMs: Multitape TMs and nondeterministic TMs 		Sec. 8.3.1–8.3.2.
Sec. 8.4.2–8.4.4
28 Dec 9 Restrictions to TMs: TMs with semi-infinite tapes.
TM and computation: the Church-Turing thesis.
Recursive languages. Complements of recursive and RE languages. 		Sec. 8.5.1.
Sec. 9.2.1–9.2.2
  Dec 16 Final Exam (6:00–8:15pm; NAC 7225)