Introduction to Automata Theory, Languages and Computation

Course Curriculum

Chapter 1: Introduction to Automata Theory, Languages and Computation

Lecture 1: Introduction to this course

Lecture 2: Introduction to Automata – Languages – Chomsky Hierarchy

Lecture 3: Formal Languages: Strings, Languages

Lecture 4: Chomsky Hierarchy

Chapter 2: Introduction to Finite Automata

Lecture 1: Introduction to Finite Automata

Lecture 2: DFA and NFA

Lecture 3: DFA – Extended Transition Function and Language Acceptance

Lecture 4: NFA – Extended Transition Function and Language Acceptance

Lecture 5: Examples of DFA and NFA – language of strings

Lecture 6: Example DFA for complement of any language

Lecture 7: Finite Automaton with €- moves

Lecture 8: Finite Representation : Regular Expressions (RE)

Lecture 9: Pumping Lemma for RE

Chapter 3: Equivalence among Finite Automata

Lecture 1: Equivalence of NFA, DFA, NFA with €- moves and RE

Lecture 2: Working and examples for Subset construction Method

Lecture 3: NFA to DFA using Lazy subset construction Method

Lecture 4: Thomson's Construction Method for RE to Ꜫ-NFA

Lecture 5: Regular Expression to DFA

Lecture 6: Solved Examples for RE to DFA

Lecture 7: Minimization of DFA

Lecture 8: Epsilon NFA to NFA

Lecture 9: DFA to RE (Formula Method)

Lecture 10: Solved Examples for DFA to RE (Formula Method)

Lecture 11: Solved Examples for DFA to RE 3 states (Formula method)

Lecture 12: DFA to RE (State Elimination Method)

Lecture 13: Finite Automata – Example 1 – Scenario Question

Lecture 14: Finite Automata – Example 2 – Scenario based question

Lecture 15: Finite Automata – Example 3 – Scenario based question for DFA construction

Chapter 4: Automata With Output

Lecture 1: Introduction to Moore and Mealy Machine

Lecture 2: Moore machine Example and Three ways of representation

Lecture 3: Mealy machine Example and Three ways of representation

Lecture 4: Moore Machine to Mealy Machine

Lecture 5: Mealy machine to Moore machine

Chapter 5: Context Free Garmmar

Lecture 1: Introduction, Types of Grammar and Representation

Lecture 2: Context Free Grammar (CFG) and Languages

Lecture 3: Derivation, Parse tree and Ambiguity

Lecture 4: Simplification of CFG – Elimination of Useless Symbols

Lecture 5: Simplification of CFG – Elimination of Null productions

Lecture 6: Simplification of CFG – Elimination of Unit productions

Lecture 7: CFG to Chomsky Normal Form (CNF)

Lecture 8: Solved Examples – CFG to CNF

Lecture 9: CFG to Greibach Normal form

Lecture 10: Solved Examples – CFG to GNF

Lecture 11: Solved Examples – CNF to GNF

Lecture 12: Example 1 – Scenario based question for CNF and GNF

Chapter 6: Push Down Automata

Lecture 1: Introduction to Push Down Automata

Lecture 2: Problem in PDA {a^nb^n/n>1}

Lecture 3: Problem in PDA {a^n b^ m/n,m>=1} two problems (n>m) and (m>n)

Lecture 4: Problem in PDA { WCW^R/ w={a,b}*}

Lecture 5: Non-Deterministic PDA {Palindrome of a string}

Lecture 6: CFG (Context Free Grammar) to PDA (Push Down Automata)

Lecture 7: PDA (Push Down Automata) to CFG (Context Free Grammar)

Lecture 8: Pumping Lemma for CFG

Lecture 9: Scenario based question in CFG and PDA

Chapter 7: Turing Machine

Lecture 1: Introduction to Turing Machine, Instantaneous Description

Lecture 2: Turing Machine Representations

Lecture 3: Turing Machine for Regular Language

Lecture 4: Turing Machine for Context Free Language

Lecture 5: TM for L={a^n b^n c^n / n>=0}

Lecture 6: TM for palindrome of a string over alphabet a,b

Lecture 7: TM for proper subtraction

Lecture 8: TM for Multiplication

Lecture 9: Modifications of TM

Lecture 10: Simulation of Turing Machine

Chapter 8: Extra solved problems in Finite Automata, Push Down Automata and Turing Machine

Lecture 1: Example 1 : Regular Language – construction of DFA, PDA and TM

Lecture 2: Example 2 : Context Free Language – Construction of PDA and TM

Lecture 3: Example 3 : Turing Machine problem

Lecture 4: Example 4 : Turing Machine for 1's Complement

Lecture 5: Example 5 : scenario based question in Turing Machine

Lecture 6: Example 6 : scenario based question in Turing Machine

Lecture 7: Example 7 : scenario based question in Turing Machine

Lecture 8: Example 8 : scenario based question in PDA and CFG

Chapter 9: Decidability and Undecidability

Lecture 1: Decidability and Undecidability

Chapter 10: Class P and Class NP problems

Lecture 1: Scenario based question in PCP