Theory of Automata &
Formal Languages
(KCA-201)
Presented by -
Dhananjay Kumar Singh
Assistant Professor
Department of Computer Application
UIM, Prayagraj
[email protected] 1
UNIT - I
2
Contents
Basic Concepts and Automata Theory:
• Introduction to Theory of Computation
– Automata, Computability and Complexity
– Alphabet, Symbol, String, Formal Languages, Deterministic
Finite Automaton
• (DFA)- Definition, Representation, Acceptability of a String
and Language
• Non Deterministic Finite Automaton (NFA)
• Equivalence of DFA and NFA
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 3
Contents cont…
• NFA with ε-Transition
• Equivalence of NFA’s with and without ε-Transition
• Finite Automata with output:-
– Moore machine, Mealy Machine, Equivalence of Moore
and Mealy Machine,
• Minimization of Finite Automata
• Myhill-Nerode Theorem
• Simulation of DFA and NFA.
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 4
Introduction
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 5
Components of Theory of Computation
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 6
Components of Theory of Computation
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 7
Concepts of Automata Theory
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 8
Finite Automata
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 9
Finite Automata
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 10
Finite Automata
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 11
Finite Automata
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 12
Deterministic Finite Automata
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 13
Deterministic Finite Automata
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 14
Examples of DFA
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 15
Examples of DFA
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 16
Examples of DFA
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 17
Transition Function
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 18
Transition Graph/ Diagram
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 19
Alphabet, String & Languages
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 20
Alphabet, String & Languages
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 21
Alphabet, String & Languages
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 22
Alphabet, String & Languages
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 23
Alphabet, String & Languages
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 24
Alphabet, String & Languages
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 25
Alphabet, String & Languages
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 26
Alphabet, String & Languages
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 27
Alphabet, String & Languages
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 28
Finite Automata
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 29
Finite Automata
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 30
DFA
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 31
NFA
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 32
States of Finite Automata
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 33
Acceptability of a string by DFA
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 34
Acceptability of a string by DFA-Solution
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 35
Acceptability of a string by NFA
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 36
Acceptability of a string by NFA-solution
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 37
Difference between DFA and NFA
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 38
Equivalence of NFA and DFA
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 39
Equivalence of NFA and DFA
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 40
Equivalence of NFA and DFA
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 41
Equivalence of NFA and DFA
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 42
Equivalence of NFA and DFA
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 43
Equivalence of NFA and DFA
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 44
Equivalence of NFA and DFA
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 45
Equivalence of NFA and DFA
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 46
NFA with Ɛ- MOVE
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 47
NFA with Ɛ- MOVE
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 48
NFA with Ɛ- MOVE
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 49
NFA with Ɛ- MOVE
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 50
NFA with Ɛ- MOVE
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 51
NFA with Ɛ- MOVE
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 52
NFA with Ɛ- MOVE
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 53
NFA with Ɛ- MOVE
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 54
FINITE AUTOMATA WITH OUTPUTS
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 55
FINITE AUTOMATA WITH OUTPUTS
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 56
MOORE MACHINE
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 57
MOORE MACHINE
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 58
MOORE MACHINE
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 59
MEALY MACHINE
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 60
MEALY MACHINE
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 61
MEALY MACHINE
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 62
EQUIVALENCE of MOORE and MEALY MACHINES
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 63
EQUIVALENCE of MOORE and MEALY MACHINES
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 64
Conversion of Moore Machine to Mealy Machine
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 65
Conversion of Moore Machine to Mealy Machine
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 66
Conversion of Moore Machine to Mealy Machine
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 67
Conversion of Moore Machine to Mealy Machine
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 68
Conversion of Moore Machine to Mealy Machine
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 69
Conversion of Moore Machine to Mealy Machine
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 70
Conversion of Mealy Machine to Moore Machine
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 71
Conversion of Mealy Machine to Moore Machine
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 72
Conversion of Mealy Machine to Moore Machine
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 73
Conversion of Mealy Machine to Moore Machine
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 74
Conversion of Mealy Machine to Moore Machine
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 75
Conversion of Mealy Machine to Moore Machine
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 76
Conversion of Mealy Machine to Moore Machine
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 77
Conversion of Mealy Machine to Moore Machine
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 78
Minimization of Finite Automata
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 79
Minimization of Finite Automata
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 80
Minimization of Finite Automata
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 81
Minimization of Finite Automata
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 82
Minimization of Finite Automata
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 83
Minimization of Finite Automata
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 84
Minimization of Finite Automata
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 85
Minimization of Finite Automata
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 86
Minimization of Finite Automata
By: Dhananjay Kumar Singh . Department of Computer Application . UIM (011) 87
Thank You
88
