Ashutosh Trivedi: Courses/CS 208

Logistics

Instructors: Supratik Chakraborty (supratik@cse), Akshay S. (akshayss@cse), and Ashutosh Trivedi (trivedi@cse)
Prerequisites CS 207 (Discrete Structures) and Programming experience
Lectures: Tuesday and Friday (10:00—noon)
Tutorials: Wednesday (10:00—noon)
Office hours: Ashutosh Trivedi (Friday 16:00—17:00), SIA 08, KReSIT Bldg.
Venue :
- Lectures and tutorials: SIC205, 2nd floor, 'C' Block, KReSIT building
- 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

Part I: Two formal models of computation: finite automata and Turing machines

Finite Memory "Automata" and their languages [trivedi]
- 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
Turing Machines (Finite automata extended with an unbounded read/write tape) and their languages [akshayss]
- 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)
[Mid-semester Exams]
Part II: Between finite automata and Turing machines: Expressiveness vs Efficiency
Pushdown Automata (Finite memory automata extended with a "Stack") and their languages [supratik]
- 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
Future Directions: Complexity Theory and Automata Theory [trivedi]
- Introduction to Complexity Classes (P, NP, NP-complete)
- Introduction to Formal Modeling and Analysis (Decidable extensions of Finite Automata such as Visibly Pushdown-Automata, Recursive State Machines, Timed Automata, Markov Decision Processes, Reversal-Bounded Counter Machines)
[End-semester Exams]

Schedule and Lecture Notes

Date	Description	Textbook References
May 17	Introduction to automata theory and some background [Slides ]	Hopcroft, Motwani, and Ullman: Chapter 1 –or– Sipser: Chapter 1
May 21	Finite Automata and their properties [Slides]	Hopcroft, Motwani, and Ullman: Section 2.1, 2.2, and 2.3 –or– Sipser: Section 1.1
May 22	Tutorial class—no new concepts were introduced.
May 24	Nondeterminism and Alternation [Slides]	Hopcroft, Motwani, and Ullman: Section 2.3, 2.4, 2.5, and 4.2–or–Sipser: Section 1.2
May 28	Regular Expressions [Slides]	Hopcroft, Motwani, and Ullman: Chapter 3–or–Sipser: Section 1.3
May 29	Tutorial class—no new concepts were introduced.
May 31	Lecture postponed to June 3rd.
June 3	Pumping Lemma, Minimization, and Myhill-Nerode Theorem [Slides]	Hopcroft, Motwani, and Ullman: Chapter 4–or–Sipser: Section 1.4
June 4	Definition of Turing machines, examples, variants, the Church Turing thesis [Slides]	Hopcroft, Motwani, and Ullman: Chapter 8–or–Sipser: Chapter 3
June 5	Tutorial class—no new concepts were introduced. Quiz.
June 7	Decidability (recursive) and Turing recognizability (r.e), Undecidable languages (the Halting problem), and some more properties of decidable and r.e languages [Slides]	Hopcroft, Motwani, and Ullman: Chapter 9 –or–Sipser:Chapter 4
June 10	Reductions, more undecidable problems, PCP, and counter machine [Slides] .
June 11	Tutorial class
June 12	Mid-Semester Exam.
June 18	Pushdown automata (PDA), acceptance by final states and empty stack, non-deterministic and deterministic PDA, Introduction to context free grammars (CFG)
June 19	More on context free grammars, tutorial

Notes

The first lecture of the course is on 17th May 2013 and the venue is SIC205, 2nd floor, 'C' Block, Kanwal Rekhi (KReSIT) building.
The instructors 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.
Instructor would like to have the lecture on Fri Jun 21 from 3-5 pm. However, if this clashes with other academic commitments, please send email to instructor by tonight (Thurs Jun 20).
Final grades are available here.

Logistics

Relevant Textbooks

Grading

Topics

Part I: Two formal models of computation: finite automata and Turing machines

Part II: Between finite automata and Turing machines: Expressiveness vs Efficiency

[End-semester Exams]

Schedule and Lecture Notes

Notes