Formal Languages and Automata
CSc 42800–Fall 2010
The City College of CUNY
Department of Computer Science
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.
|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.
|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),
|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,
|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.|
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|
||Double slot to make-up class of Sep 21.
The pumping lemma for regular languages. Examples.
|Double slot to make-up class of Sep 23.
Closure properties of regular languages.
|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!
|17||Oct 28||Midterm Exam|
|18||Nov 2||Ambiguous and non-ambiguous grammar. Inherently ambiguous
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
|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 7.1, 7.1.1-7.1.2
|Double slot to make-up class of
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.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
|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.
|Dec 16||Final Exam (6:00–8:15pm; NAC 7225)|