Finite Automata
THEORY OF AUTOMATA
Group Members
• Zahra (90
)
• Aliza
(101)
Introduce
Finite Automata
Finite Automata was
first introduced in
1943. It came from
efforts to
understand how
machines and the
human brain
process information.
Who Invented It?
The concept was first They published a famous
described by Warren paper called “A Logical
McCulloch and Walter Calculus Immanent in
- Neural networks
Pitts, two Nervous Activity” which
neurophysiologists. laid the foundation for:
- Automata theory - Computation theory - Cybernetics
What is Finite Automata?
A Finite Automaton (FA) is a simple machine
that reads input symbols (letters) and decides
whether to accept or reject the string.
It has multiple states, and on each input, it moves from
one state to another based on a transition rule.
Example
• Example 1: Traffic Light
•States: {Red, Green, Yellow}
•Input: Timer signal
•Transitions:
•Red → Green
•Green → Yellow
•Yellow → Red
•Explanation:
A traffic light has a finite number of states and moves from one
state to another based on the timer.
• FA = {Q, Σ, q0, F, δ}
Formal • Q = Set of states
Definition of Finite • Σ = Set of input symbols
(Alphabet)
Automata: • q0 = Starting state
• F = Final states (Accepting
states)
• δ = Transition function
Representation of finite
Automata:
Two Types of Finite
Automata:
• DFA (Deterministic Finite
Automata)
Types of • NFA (Non-Deterministic Finite
Finite Automata)
Automata Brief Description:
• Each input leads to only one
next state
• An input can lead to multiple
possible states
Field Purpose
Compiler Design Used for lexical
analysis
Networking Validates protocols
Importance
of Finite Text Editors Matches patterns
Automata and searches
Game AI Controls character
movements
Where Is It Used?
Fields is it used Programming Networking Robotics AI
Lexical TCP/IP protocol Decision- Basic decision
Examples analyzer in checking making for trees
compilers movements
Easy Summary
FA is a machine that reads DFA has clear next steps. NFA has multiple possible It's the foundation of
letters and decides if the paths. automata theory and helps
full word (string) is valid. build smarter machines
like Turing Machines.
1:Video Games & AI
Behavior:
• Game engines use finite
automata to model AI decision-
making — like enemy movement
or dialogue trees.
• For example, games like Warcraft Modern
3 use state machines to control
complex behaviors. technology of
2: Digital Circuit
finite
Design: Automata
• Finite automata are used to
design sequential circuits in
devices like washing machines,
fans, and refrigerators.
• These circuits follow specific
state transitions to perform tasks
reliably.
3:Biomedical Imaging:
Technologies like X-ray diffraction
use automata algorithms to
process image data.
Continue…
They help generate accurate
diagnostic visuals by following
structured scanning patterns.
Creation of FA :
• Given the regular expression
a* , which represents a
language of strings starting
with zero or more as followed
by one or more bs:
• Construct a Finite Automaton
(FA) for this regular expression.
Example… Regular Expression: a*
a*→ zero or more
occurrences of 'a'
→ one or more
occurrences of 'b'
String a*
Accepted Strings by This FA Rejected Strings by This FA
b empty
ab a
aaab aa
abbbb aba
aaaaabbbbbb ba
State diagram of a*
∑ ¿{𝑎 ,𝑏} Q={ }
+ ¿¿
a* 𝑏 a*
Start state final state
Transition Table:
Transition Function:
δ(q0, a) = q0
δ(q0, b) = q1
δ(q1, b) = q1
a b
Acceptance of FA
• A string is accepted by a
Finite Automaton (FA) if:
• It starts at the initial state
• Follows valid transitions for
every input symbol
• Ends in a final (accepting)
state
Example:
b
ab
aaab
Rejectance of FA
• A string is rejected by a
Finite Automaton (FA) if:
• Not ends in a final
(accepting) state
Example:
• empty
•a
• ba
limitations of FA:
Cannot count
Cannot handle
arbitrary
Limited nested or
symbols (like
memory recursive
equal a’s and
structures
b’s)
Cannot parse
Only accepts context-free or
regular context-
languages sensitive
languages
Limitations:
No backtracking capability
Cannot perform arithmetic or logic operations
State explosion for complex patterns
Inflexible to input variations
No stack or deep memory like in Pushdown Automata
Thank you 😊
For your
listening…
