Formal Languages and AutomataCSc 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, SH279
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 ]
Prerequisites: CSc 30400.
The grades for the midterm and final exams will be combined as follows:
Late Assignment Policy: Homework are due at the beginning of the class on the due date. Late assignment will not be accepted.
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 makeup 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. Makeup 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. Makeup class on Oct. 5, 6:15–7:30pm, Room HR 11  
Sep 23  No class. Makeup 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.13.2.2 
7  Sep 30  From regular expressions to automata. Applications of RE's. Algebraic laws for RE.  Sec. 3.2.3. Sec. 3.33.4 
8–9  Oct 5 
Double slot to makeup 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 makeup 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 MyhillNerode Theorem.  Sec. 4.4 
14  Oct 19  Contextfree grammars (CFG). Parse trees.  Sec. 5.15.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 nonambiguous 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.16.2.2 
20  Nov 9  Equivalence of acceptance by final state and by empty stack. Examples. Discussion of the midterm 
Sec. 6.2.36.2.4 
Nov 11  No class. Makeup 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.17.1.2 
23–24  Nov 23 5:00–7:30pm 
Double slot to makeup class of
Nov. 11. Eliminating ε and unit productions. Chomsky Normal Form. The pumping lemma for contextfree languages. Examples. Closure and decision properties of contextfree 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! Contextsensitive 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 semiinfinite tapes. TM and computation: the ChurchTuring 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) 