CS 310 : Automata Theory 2019
Instructors : Ashutosh Gupta and
S. Akshay
Timings : 9:30 Monday, 10:35 Tuesday, 11:35 Thursday
Venue : CC103
TAs :
Adarsh Rahul Jaju (173050003@),
Kalyani Dole (163050022@),
Kunal Mittal (kunal@cse),
Mukesh Pareek (pareek@cse),
Prachi Singh (183050075@),
Swapnam Bajpai (swapnam@cse),
Vaibhav Krishan (vkrishan@cse),
Meet Taraviya (meet11061997 _at_ gmail.com)
For email addresses Append ".iitb.ac.in" in the text inside the parenthesis
Optional tutorials : 7PM,Tuesday@CC103
Source material
- Introduction to Automata Theory, Languages, and Computation. John Hopcroft, Rajeev Motwani, and Jeffrey Ullman
Evaluation structure
- Attendance: 5%
- Quizzes : 30% (4 quizzes)
- Midterm : 25% (2 hours)
- Final : 40% (3 hours)
Random attendance status
May change later.
Tutorial sheets
Lectures
Introduction
2019-01-03 : Lecture 1 - Introduction to automata theory
- what is computing?, modelling computer
- Words, states, transitions, automaton
- languages
- slides
- Suggested reading : Hopcroft sections 1.1, 1.5, and 2.1
- Suggested reading for understanding formal proofs : Hopcroft sections 1.2-1.4
Finite automata
2019-01-07 : Lecture 2 - Deterministic finite automaton
- Formal definitions of DFA
- Run of DFA, extended transitions, language of DFA
- slides
- Suggested reading : Hopcroft sections 2.2
2019-01-08 : Lecture 3 - Nondeterministic finite automaton(NFA)
- Examples of DFAs
- Nondeterminism, Nondeterministic finite automaton
- slides
- Suggested reading : Hopcroft sections 2.3-2.3.4
2019-01-10 : Lecture 4 - Subset construction
- Subset construction, worklist based algorithm, lower bound
- slides
- Suggested reading : Hopcroft sections 2.3-2.3.5-2.3.6
2019-01-14 : Lecture 5 - Epsilon NFA
- finish DFA lower bound, ε-NFA
- slides
- Suggested reading : Hopcroft section 2.5
Regular expressions
2019-01-15 : Lecture 6 - Regular expressions
- Regular expressions (RE), interpretations of RE
- Usage of RE in practical programming
- slides
- Suggested reading : Hopcroft section 3.1
2019-01-17 : Lecture 7 - Regular expressions == DFA
- NFA to RE, RE to NFA, implementing regular expression search
- slides
- Suggested reading : Hopcroft section 3.2.1 and 3.2.3
- Suggested reading : Discussion RE engines
Regular languages
2019-01-21 : Lecture 8 - Properties of regular languages
- Practical RE, RE simplification laws
- Colusre properties union, intersection, complementation, and difference
- slides
- Suggested reading : Hopcroft section 3.4 and 4.2.1
2019-01-22 : Lecture 9 - Properties of regular languages II
- Closure properties: reversal, homomorphism, reverse homomorphism
- Decision problems: emptiness and membership
- slides
- Suggested reading : Hopcroft section 4.2.2-3
2019-01-24 : Lecture 10 - Pumping lemma
- Pumping lemma, contrapositive of pumping lemma
- slides
- Suggested reading : Hopcroft section 4.1.1
2019-01-25T08:30 (Friday) : Quiz 1 @CC101,103,105
2019-01-28 : Lecture 11 - Pumping lemma applications
- Application examples
- slides
- Suggested reading : Hopcroft section 4.1.2
2019-01-29 : Lecture 12 - Regular languages equivalence
- Distinguishable states, equivalent states, automaton equivalence
- Table filling algorithm
- slides
- Suggested reading : Hopcroft section 4.4.1 and 4.4.2
2019-01-31 : Lecture 13 - DFA minimization and Myhill-Norde theorem
- DFA minimization, Unique minimal DFA,
- Residual languages, Myhill-Norde theorem
- slides
- Suggested reading : Hopcroft section 4.4.3 and 4.4.4
Context-free grammars and languages
2019-02-04 : Lecture 14 - Context-free grammars
- Context-free grammers, production rules, derivations, context-free languages
- slides
- Suggested reading : Hopcroft section 5.1
2019-02-05 : Lecture 15 - Parse trees and ambiguity in grammars
- Parse tree, ambiguous grammars, removing ambiguity, inherently ambiguous grammars
- slides
- Suggested reading : Hopcroft section 5.2, 5.4
Pushdown automata
2019-02-07 : Lecture 16 - Pushdown automaton(PDA)
- Adding stack to automaton, stack symbols
- PDA definitions and language of PDAs
- slides
- Suggested reading : Hopcroft section 6.1,6.2.1-2
2019-02-11 : Lecture 17 - PDA and CFG
- Accepting by final state == empty stack
- CFG to PDA
- slides
- Suggested reading : Hopcroft section 6.2.3-4,6.3.1
2019-02-12 : Lecture 18 - PDA to CFG and deterministic PDA(DPDA)
- slides
- Suggested reading : Hopcroft section 6.3.2, 6.4
2019-02-13T08:30(Wednesday) : Quiz 2 @SIC201,SIC205,SIC301,SIC305
CFL properties
2019-02-14 : Lecture 19 - Chomsky normal form(CNF)
- slides
- Suggested reading : Hopcroft section 7.1
2019-02-18 : Lecture 20 - Pumping lemma for CFLs
- slides
- Suggested reading : Hopcroft section 7.2
2019-02-19 : Lecture 21 - Applications of CFGs
- Chart parsing, CYK parsing, Earley parsing
- slides
- Suggested reading : Wikipedia articles on the above parsing methods
2019-02-22 : Lecture 22 - Extra tutorial
- Content overflow from lecture 21
- Remaining time free discussion
- Best of luck for the midterm!
2018-02-23T11:00-13:00@LA002 : Midterm
Lectures 23+
Lectures after midterm
Last modified: ()