Theory of Automata

NFA to DFA Conversion Part - 1 (New Video)

Please watch the following video. It is your lesson for 23-03-2020.

NFA to DFA Conversion Part - 2 & 3 (New Videos)

Please watch the following videos. It is your lesson for 24-03-2020.

NFA to DFA Conversion Part - 4 (New Video)

Please watch the following video. It is your lesson for 25-03-2020.

Regular Expression to NFA with epsilon Conversion (Part-1 & 2) (New Videos)

Please watch the following videos. It is your lesson for 26-03-2020.

Before Mid-Term Topics Videos

What is 'Theory of Automata'? Why do we study it?

Theory of Automata - Introduction (PPT slides)

Context Free Grammars - Introduction

CFG - Introduction (PPT slides)

Context Free Grammars - How to design CFGs?

Simplification of CFGs - Removal of Useless Symbols

Removal of Null Productions from CFG

Removal of Unit Productions from CFG

Conversion of CFG to CNF

Correction: In the solution for example #3 (of the following video), the fourth line of CNF starts with R3 rather than R4.

Ambiguous Grammars

Regular Expressions

Deterministic Finite Automata (Part-1)

Deterministic Finite Automata (Part-2)

Deterministic Finite Automata (Part - 3)

Conversion of Regular Expression to NFA with epsilon

Conversion of NFA/DFA to Regular Expression

Mid-Term Revision (Part-1)

Mid-Term Revision (Part-2)

After Mid-Term Topics Videos

Mealy Machine Example from Spring 2018 Exam Paper*

Solved MCQs of "Theory of Automata" Spring 2018 Final Exam*

Solved True/False Questions Spring 2018 "Theory of Automata" Final Exam*

PDA Example: 00a^ncb^n11*

Non-Deterministic Push Down Automata (NPDA) for Palindrome Language*

Turing Machine Example from Spring 2018 Final Exam Paper*

Turing Machine for Unary to Binary Conversion*

Turing Machine for the Subtraction Operation

Turing Machine for {WcW | W belongs to (a,b)*} *

Pumping Lemma for 0^p where p is a prime number*

Pumping Lemma Example for Language of Binary Strings with Consecutive Ones Once only (in Urdu)

Sample Fill in the Blank for "Theory of Automata"*

Theory of Automata - Objective Questions*

An important Turing Machine Example*

Pumping Lemma for a Language that is Union of Even Numbers and Prime Numbers*

Teaching Plan

Teaching Plan Spring 2019

Useful Videos

Conversion of epsilon-NFA to NFA (Example# 1)

Conversion of epsilon-NFA to NFA (Example# 2)

Conversion of NFA to DFA (Example #1)

Conversion of NFA to DFA (Example #2)

Conversion of NFA to DFA (Example #3) Please Note: In this video, there is a mistake , state {A,B,C,D} on 'a' goes to {A,B,C,D}.

Conversion of DFA to Regular Expression (State elimination Method) Part-1

Conversion of DFA to Regular Expression (State elimination Method) Part-2

Conversion of DFA to Regular Expression (State elimination Method) Part-3

Moore Machine and Mealy Machine (Introduction)

Example #1 (Moore Machine):

Example #2 (Moore Machine):

Example #3 (Moore Machine):

Moore to Mealy Conversion (Example #1)

Moore to Mealy Conversion (Example #2)

Minimization of DFA (Example #1)

Minimization of DFA (Example #2)

Minimization of DFA (Example #3)

Minimization of DFA (Example #4)

Minimization of DFA (Example #5)

Minimization of DFA (Example #6)

Minimization of DFA (Example #7)

PDA explanation and examples

More PDA Examples

Another PDA Example