CS208: Automata Theory and Logic

### 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

 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

1. 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
• Properties of regular languages
• Non-regular languages and pumping lemma

2. 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

3. 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

4. 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)

### 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.