![]() |
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, 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 ]
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 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) |