Title: "Why Study Automata Theory?
and Different Kinds of
Automata"
Automaton = A self-operating machine or
mechanism (Dictionary definition), plural is
Automata.
Automata = abstract computing devices
Automata theory = the study of abstract
machines (or more appropriately, abstract
'mathematical' machines or systems), and the
computational problems that can be solved
using these machines.
Automata in another way
An automaton is an abstract machine that processes input strings and
transitions between states according to defined rules.
Purpose:
Models the behavior of computational systems.
Helps in the design and analysis of hardware and software.
Computation
CPU memory
5
temporary memory
input memory
CPU
output memory
Program memory
6
3
Example: f ( x ) x
temporary memory
input memory
CPU
output memory
Program memory
compute xx
2
compute x x 7
3
f ( x) x
temporary memory
input memory
x 2
CPU
output memory
Program memory
compute xx
2
compute x x 8
3
temporary memory f ( x) x
z 2 * 2 4
f ( x) z * 2 8
input memory
x 2
CPU
output memory
Program memory
compute xx
2
compute x x 9
3
temporary memory f ( x) x
z 2 * 2 4
f ( x) z * 2 8
input memory
x 2
CPU
f ( x) 8
Program memory output memory
compute xx
2
compute x x 10
Automaton
temporary memory
Automaton
input memory
CPU
output memory
Program memory
11
Automata are distinguished by the temporary memo
• Finite Automata: no temporary memory
• Pushdown Automata: stack
• Turing Machines: random access memory
12
Finite Automaton
temporary memory
input memory
Finite
Automaton
output memory
Example: Automatic Door, Vending Machines
(small computing power)
13
Pushdown Automaton
Stack Push, Pop
input memory
Pushdown
Automaton
output memory
Example: Compilers for Programming Languages
(medium computing power) 14
Turing Machine
Random Access
Memory
input memory
Turing
Machine
output memory
Examples: Any Algorithm
(highest computing power) 15
Power of Automata
Finite Pushdown Turing
Automata Automata Machine
Less power More power
Solve more
computational problems
16
A simple computer
H
I TC
SW
BATTERY
input: switch
output: light bulb
actions: flip
switch
states: on, off
A simple “computer”
H
I TC
SW
BATTERY start off on
input: switch
output: light bulb bulb is on if and only
if there was an odd
actions: f for “flip number of flips
switch”
states: on, off
Another “computer”
1
1 start off off
1
2 2 2 2
BATTERY
1
2
off on
1
inputs: switches 1 and
2 bulb is on if and only
actions: 1 for “flip if both switches were
switch 1” flipped an odd
actions: 2 for “flip number of times
switch 2”
states: on, off
Mathematical Preliminaries
• Sets
• Functions
• Relations
• Graphs
• Proof Techniques
20
SETS
A set is a collection of elements
A {1, 2, 3}
B {train, bus, bicycle, airplane}
We write
1 A
ship B
21
Set Representations
C = { a, b, c, d, e, f, g, h, i, j, k }
C = { a, b, …, k } finite set
S = { 2, 4, 6, … } infinite set
S = { j : j > 0, and j = 2k for some
k>0 }
S = { j : j is nonnegative and even } 22
A = { 1, 2, 3, 4, 5 }
U
6 A
2 3 8
1
7 4 5
9
10
Universal Set: all possible elements
U = { 1 , … , 10 }
23
Set Operations
A = { 1, 2, 3 } B = { 2, 3, 4, 5}
• Union A B
2 4
1
A U B = { 1, 2, 3, 4, 5 } 3 5
• Intersection
A U B = { 2, 3 } 2
3
• Difference
A-B={1} 1
B - A = { 4, 5 } 4
Venn diagrams 5 24
• Complement
Universal set = {1, …, 7}
A = { 1, 2, 3 } A = { 4, 5, 6, 7}
4
A
A 3 6
1
2
5 7
A=A
25
{ even integers } = { odd
integers }
Integers
1 odd
even 5
2 6
0
4
3 7
26
DeMorgan’s Laws
U
AUB=A B
U
A B=AUB
27
Empty, Null Set:
={}
SU =S
U
S = = Universal Set
S- =S
-S=
28
Subset
A = { 1, 2, 3} B = { 1, 2, 3, 4, 5 }
A B
U
Proper Subset: A B
U
B
A
29
Disjoint Sets
A = { 1, 2, 3 } B = { 5, 6}
U
A B=
A B
30
Set Cardinality
• For finite sets
A = { 2, 5, 7 }
|A| = 3
(set size)
31
Powersets
A powerset is a set of sets
S = { a, b, c }
Powerset of S = the set of all the subsets of S
={ , {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c
Observation: | 2S | = 2|S| ( 8 = 23 )
32
Cartesian Product
A = { 2, 4 } B = { 2, 3, 5 }
A X B = { (2, 2), (2, 3), (2, 5), ( 4, 2), (4, 3), (4, 5) }
|A X B| = |A| |B|
Generalizes to more than two sets
AXBX…XZ
33
FUNCTIONS
domain range
4 A B
f(1) = a a
1
2 b
3 c
5
f : A -> B
If A = domain
then f is a total function
otherwise f is a partial function
34
RELATIONS
Let A & B be sets. A binary relation “R” from A to B
R = {(x1, y1), (x2, y2), (x3, y3), …}
Where xi Aand yi B
R⊆AxB
xi R yi to denote ( a, b) R
e. g. if R = ‘>’: 2 > 1, 3 > 2, 3 > 1
35
GRAPHS
A directed graph
e
b
node
a d
ed g e c
Nodes (Vertices)
V = { a, b, c, d, e }
Edges
E = { (a,b), (b,c), (b,e),(c,a), (c,e), (d,c), (e,b), (e,d)
36
Labeled Graph
2
6 e
b 2
1 3
a 6 d
5
c
37
Walk
e
b
a d
Walk is a sequence of adjacent edges
(e, d), (d, c), (c, a)
38
Path
e
b
a d
Path is a walk where no edge is repeated
Simple path: no node is repeated
39
Cycle
base e
b
3
a 1 d
2
c
Cycle: a walk from a node (base) to itself
Simple cycle: only the base node is repeated
40
Euler Tour
8 base
7 e
b 1
4 6
a 5 2 d
3
c
A cycle that contains each edge once
41
Hamiltonian Cycle
5 base
e
b 1
4
a 2 d
3
c
A simple cycle that contains all nodes
42
Trees
root
parent
leaf
child
Trees have no cycles
43
root
Level 0
Level 1
leaf Height 3
Level 2
Level 3
44
Binary Trees
45
Introduction to Proof techniques
Purpose of Proofs:
Establish the truth of mathematical statements.
Provide a logical foundation for theories and applications.
Importance in Discrete Mathematics:
Essential for validating algorithms and structures.
Ensures the correctness of combinatorial arguments.
1. Direct Proof
2. Proof by Contradiction
Definition:
Assume the negation of the statement to be proved and show that this
assumption leads to a contradiction.
3. Proof by Contraposition
4. Proof by Induction
5. Proof by Cases
Conclusion
Understanding various proof techniques is crucial in
discrete mathematics.
Each method provides a different approach to
establishing mathematical truths.
