CS208: Automata Theory and Logic (Spring 2014)

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

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

### Topics

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

[Mid-semester Exams]
2. 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

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