Ashutosh Trivedi: Courses/CS 208

Logistics

Instructor: Ashutosh Trivedi (trivedi@cse)
Teaching Assistants : Hemant Adil, Nishanth Dikkala, Umang Mathur, Vipul Singh .
Prerequisites CS 207 (Discrete Structures)
Lectures: Monday (10:35am—11:30am), Tuesday (11:35am—12:30pm) and Thursday (8:30am—9:30am)
Tutorials: TBA
Office hours: Ashutosh Trivedi (Thursday 10:00am—11:00am), SIA 08, KReSIT Bldg.
Venue :
- Lectures: LCC12
- Tutorials: TBA
- Office hours: SIA 108, 1st floor, 'A' Block, KReSIT building

Relevant Textbooks

Main Reference

J. E. Hopcroft, R. Motwani and J. D. Ullman. Introduction to Automata Theory, Languages and Computation
Low priced paperback edition published by Pearson Education.

Supplementary Reading

Michael Sipser. Introduction to the Theory of Computation
PWS Publishing Company.
H. R. Lewis and C. H. Papadimitriou. Elements of the Theory of Computation
Eastern economy edition published by Prentice Hall of India Pvt. Ltd.
Dexter Kozen, Automata and Computability
Springer-Verlag New York Incorporated, 1997.

Grading

End-Semester Exams: 50%
Mid-Semester Exams: 30%
Quizzes: 10%
Class participation: 10%

Topics

Finite Memory "Automata" and their languages
- Motivation
- Finite State Automata (DFAs)
- Non-deterministic Finite State Automata (NFAs)
- NFA = DFA
- "Regularity" of languages accepted by DFAs (NFAs)
  - Regular expressions
  - Applications
  - Monadic Second-Order Logic
- Properties of regular languages
- Non-regular languages and pumping lemma
[Mid-semester Exams]
Pushdown Automata (Finite memory automata extended with a "Stack") and their languages
- Motivation
- Deterministic Pushdown automata (DPAs)
- Non-deterministic Pushdown automata (NPAs)
- NPA $\not = $DPA.
- "Context-free" languages accepted by NFA
  - Context-Free Grammar and their languages
  - Applications
  - Equivalence of languages captured by NPAs and CFGs
- properties of languages captured by NPAs
- languages captured by DPAs
- Non-context-free languages and pumping lemma
- Multistack pushdown automata
- Counter machines: multistack automata with single stack symbol
Turing Machines (Finite automata extended with an unbounded read/write tape) and their languages
- Motivation: an idealised model of a computer
- Turing machines (TMs) (Watch TM in action here and here )
- Non-deterministic Turing machines (NTMs)
- TM = NTM
- Adding more tapes to TMs
- TMs and computers
- Recursively-enumerable (semi-algorithm) vs Recursive languages (algorithms)
- Undecidability and the Halting problem
- Other Undecidable Problems (Post Correspondance Problem and Counter machines)

Schedule and Lecture Notes

#	Date	Description	Textbook References
1	Jan 13	Introduction to automata theory [Slides ]	Hopcroft, Motwani, and Ullman: Chapter 1
2	Jan 16	Introduction to automata theory [Slides ]	Hopcroft, Motwani, and Ullman: Chapter 1
3	Jan 20	Introduction to propositional and first-order logic	Guest lecture by Khushraj Madnani
4	Jan 21	Introduction to propositional and first-order logic	Guest lecture by Khushraj Madnani
5	Jan 23	Deterministic Finite Automata: syntax and semantics (via computation and via extended transition function), some simple examples. [Slides ]	Hopcroft, Motwani, and Ullman: Section 2.1 and 2.2, and Sipser Section 1.1
6	Jan 27	Deterministic Finite Automata: product construction for union and intersection [Slides ]	Hopcroft, Motwani, and Ullman: Section 4.2.1, and Sipser Section 1.1
7	Jan 28	Deterministic Finite Automata: product construction contd., complementation, problems with concatenation and Kleene closure as a motivation for non-determinism. [Slides ]	Hopcroft, Motwani, and Ullman: Section 4.2.1 and Section 2.3, and Sipser Section 1.2
8	Jan 30	Nondeterministic Finite Automata: the notion of acceptance via extended transition function and computation tree, $\varepsilon$- transitions, [Slides ]	Hopcroft, Motwani, and Ullman: Section 2.3 to 2.5, and Sipser Section 1.2
9	Feb 3	Subset Construction [Slides ]	Hopcroft, Motwani, and Ullman: Section 2.3.5 and 2.3.6, and Sipser Section 1.2
10	Feb 4	Regular Expressions: introduction, regular expressions to DFA conversion, and DFA to regular expressions conversion (by eliminating the states) [Slides ]	Hopcroft, Motwani, and Ullman: Section 3.1, 3.2.2, and 3.2.3, and Sipser Section 1.3
11	Feb 6	Regular Expressions Contd.: Algebraic laws for regular expressions	Hopcroft, Motwani, and Ullman: Section 3.4
*	Feb 10	Class Cancelled
12	Feb 11	Regular Expressions: Correctness proof for the equivalence of DFA and Regular expressions	Hopcroft, Motwani, and Ullman: Chapter 3
*	Feb 12	[ Quiz 1 ]
*	Feb 17	Mid-Semester Week
*	Feb 19	[ Mid-Semester Exam ]
*	Feb 20	Mid-Semester Week
13	Feb 24	Decision Properties of Regular Languages: Closure under Boolean operations, Regular Operations, Reversal, and homomorpshism	Hopcroft, Motwani, and Ullman: Section 4.2
14	Feb 25	Closure under Homomorphism and inverse-homomorphism; decision properties of regular languages	Hopcroft, Motwani, and Ullman: Section 4.2 and 4.3
15	Feb 27	Equivalence and Minimization of Automata [Slides ]	Hopcroft, Motwani, and Ullman: Section 4.4
16	Mar 3	Equivalence and Minimization of Automata and Myhill-Nerode Theorem [Slides ]	Hopcroft, Motwani, and Ullman: Section 4.4
17	Mar 4	Pumping Lemma for regular languages [Slides ]	Hopcroft, Motwani, and Ullman: Section 4.1
18	Mar 6	Pumping Lemma (examples) [Slides ]	Hopcroft, Motwani, and Ullman: Section 4.1
19	Mar 10	Chomsky's grammar hierarchy [Slides ]	Hopcroft, Motwani, and Ullman: Chapter 5 and Sipser Chapter 2
20	Mar 11	Context-Free Languages [Slides ]	Hopcroft, Motwani, and Ullman: Chapter 5 and Sipser Chapter 2
21	Mar 13	Context-Free Languages: Examples, and the concept of derivation, (leftmost and rightmost derivation), parse trees [Slides ]	Hopcroft, Motwani, and Ullman: Chapter 5 and Sipser Chapter 2
*	Mar 17	Institute holiday
*	Mar 18	Lecture cancelled due to student's request
22	Mar 20	In-class Quiz.
23	Mar 24	Pushdown Automata [Slides ]	Hopcroft, Motwani, and Ullman: Chapter 6 and Sipser Chapter 2
18	Mar 25	Equivalence of acceptance by empty stack and final states [Slides ]	Hopcroft, Motwani, and Ullman: Chapter 6 and Sipser Chapter 2
24	Mar 27	Equivalence of CFGs and PDAs [Slides ]	Hopcroft, Motwani, and Ullman: Chapter 6 and Sipser Chapter 2
*	Mar 31	Institute Holiday
25	Apr 1	Properties of CFLs: Pumping lemma [Slides ]	Hopcroft, Motwani, and Ullman: Chapter 7 and Sipser Chapter 2
26	Apr 3-15	Turing machines [Slides ]	Hopcroft, Motwani, and Ullman: Chapter 8 and 9 and Sipser Chapter 3, 4, 5

Notes

The first lecture of the course is on 13th Jan 2014.
The instructor reserve the right to admit students coming late to class.
The webpage of a previous offering of the course is available here . This page offers a number of practice questions and quizzes. Also, please go through the ground rules regarding dishonest and unethical activities. In this offering of the course we shall stick to these rules.
We are now using Piazza for class discussion. Please use this system to get quick help from classmates, TAs, and instuctors. Rather than emailing questions to the teaching staff, the instructor encourages you to post your questions on Piazza. Find our class page at: https://piazza.com/iitb.ac.in/spring2014/cs208/home.
The endsemester exam for the course is scheduled on Tuesday 22nd April from 14:00 To 17:00 in Hall 3.