Automata Theory | Theory of Computation Beginner to advanced

Course Curriculum

Chapter 1: Introduction

Lecture 1: Introduction to Automata Theory and its significance

Lecture 2: Instructor Introduction

Lecture 3: Fundamentals

Chapter 2: Finite State Automata

Lecture 1: Deterministic Finite State Automata (DFA)

Lecture 2: Representation of Finite Automata

Lecture 3: Extended Transition Function

Chapter 3: Design of Finite Automata

Lecture 1: Introduction to JFLAP

Lecture 2: Designing Finite Automata with JFLAP

Lecture 3: Simulating FA in JFLAP

Lecture 4: FA accept all the strings of a's and b's starting with 'ab'

Lecture 5: FA accept all the strings of a's and b's ends with 'aa'

Lecture 6: FA accept all the strings starts and ends with the same symbol

Lecture 7: Every string contain substring 'aba'

Lecture 8: 3rd symbol from left end is always 'b'

Lecture 9: Design problem on number of alphabets in string

Lecture 10: Every string contain an odd number of 0's and an even number of 1's

Lecture 11: Design problem on length of string

Lecture 12: Design problem on string not contain a particular substring

Lecture 13: Practical Application

Chapter 4: DFA Minimisation

Lecture 1: Myhill-Nerode Theorem

Lecture 2: Minimal State FA Computation

Chapter 5: Non Deterministic Finite Automata (FA)

Lecture 1: Nondeterministic Finite Automata (NFA)

Lecture 2: Comparison of NFA & DFA

Lecture 3: Extended transition function

Lecture 4: Conversion of NFA to DFA

Lecture 5: Equivalence of Deterministic and Nondeterministic Finite Automata

Chapter 6: Finite Automata with Epsilon Transition

Lecture 1: Finite Automata with Epsilon Transitions

Lecture 2: Epsilon Closure

Lecture 3: Conversion of Epsilon NFA to NFA

Lecture 4: Extended Transition Function

Chapter 7: Finite State Machines with Output

Lecture 1: Moore machine

Lecture 2: Design of Moore machine which counts the occurrence of substring 'aab'

Lecture 3: Mealy machine

Lecture 4: Design of Mealy machine which print 1's complement of a number

Lecture 5: Comparison of Moore machine and Mealy machine

Lecture 6: Two- Way Finite Automata

Chapter 8: Regular Expressions

Lecture 1: Regular Expressions

Lecture 2: Building Regular Expressions 1

Lecture 3: Building Regular Expressions 2

Lecture 4: Converting Regex to Epsilon NFA

Lecture 5: Converting Regular Expressions (ab+a)* to NFA with epsilon transitions

Lecture 6: Equivalence of regular expressions and NFA with epsilon transitions

Lecture 7: Converting DFA to Regular Expressions

Lecture 8: Regex DFA Conversion example

Chapter 9: Regular Languages

Lecture 1: Regular Language: Language of Automata

Lecture 2: Pumping Lemma for Regular Languages

Lecture 3: Applications of the Pumping Lemma

Lecture 4: Proof for Pumping Lemma

Lecture 5: Closure Properties of Regular sets

Lecture 6: Proof and Example for closure properties

Chapter 10: Context Free Languages

Lecture 1: Context Free Grammar

Lecture 2: Design of CFG for L={a^nb^n/n>0}

Lecture 3: Design CFG for L={wcw^R/ w is in (0+1)*}

Lecture 4: Design of CFG for string of balanced parentheses

Lecture 5: CFG for string having Equal number of a's and b's

Lecture 6: Leftmost and Rightmost Derivation

Lecture 7: Derivation Tree / Parse Tree

Lecture 8: Ambiguous Grammar

Lecture 9: Closure properties of CFL

Lecture 10: Decision problems associated with CFL

Lecture 11: Pumping lemma for CFL

Lecture 12: Application of pumping lemma

Chapter 11: Normal Forms for CFL

Lecture 1: Simplification of CFG

Lecture 2: Chomsky Normal Form

Lecture 3: Left Recursive Grammar

Lecture 4: Greibach normal forms