Finite Automaton : Formal Definition.
Finite Automaton is a simple idealized
machine used to recognize patterns within input taken from some character set
called an alphabet. The job of a finite automaton is to accept an input
depending on whether the pattern defined by the finite automaton occurs in the
input.
A
finite automaton (an abstraction of a computer) is a finite representation of a
formal language that may be an infinite set. (Automata is plural, singular is
automaton) A finite automaton is a model of a particularly simple computing
device that acts as a language acceptor.
Finite automaton, also known as Finite State
Machine (FSM) is a mathematical model of computing used in the design of
computer programs and sequential logic circuits. They are not actual machines,
but abstract machines that may be in any one of some limited number of states
at one time.
Formal Definition of Finite Automaton.
A Finite
Automaton is mathematically defined as a 5-tuple:
M = (Q, Σ, δ, q0, F)
Where:
i.
Q is a finite set of states
ii.
Σ is a finite set of symbols called the alphabet
iii.
δ (delta) is the transition function
iv.
q0 is the start state (an element of
Q)
v.
F is the set of accept states (a
subset of Q)
Explanation of Each Tuple:
1. Finite Set of States
·
This is a non-empty set containing
all possible states the automaton can be in.
·
The automaton can only be in one
state at any given time.
Example:
In a light switch example:
Q = {ON, OFF}
The switch can either be ON or OFF.
2. Σ (Sigma): Finite Set of Input Symbols (Alphabet)
The
alphabet is a set of symbols that the automaton can read as input.
Example:
For an automaton that processes binary strings:
Σ = {0, 1}
3. δ (Delta): Transition Function
·
Defines how the automaton moves from
one state to another based on the current state and the input symbol.
·
It takes a state from Q and a
symbol from Σ and returns the next state.
·
For each state and input symbol,
exactly one next state is specified (this makes the automaton deterministic).
Example:
Suppose:
·
Q = {S0, S1}
·
Σ = {a, b}
The
transition function δ is defined as:
·
δ(S0, a) = S1
·
δ(S0, b) = S0
·
δ(S1, a) = S0
·
δ(S1, b) = S1
This
means:
·
If the automaton is in state S0
and reads ‘a’, it transitions to state S1.
·
If it’s in state S0 and reads ‘b’,
it stays in S0, and so on.
4. q0: Start State
·
The state where the automaton
begins processing the input string.
·
Must be an element of the set of
states Q.
Example:
For an automaton recognizing strings with an odd number of 1’s:
q0 = S0
5. F: Set of Accept States (Final States)
·
A subset of Q.
·
If the automaton ends its
computation in any of these states after reading the entire input, the string
is accepted.
·
If it ends in a state not in F,
the string is rejected.
Example:
For the automaton recognizing strings with an odd number of 1’s:
F = {S1}
Examples and Acceptability of String.
How Strings are Accepted or Rejected by a Finite Automaton
Acceptability of Strings
A finite
automaton reads an input string one symbol at a time. It changes its state
according to its transition function. Whether a string is accepted or rejected
depends on the final state the automaton reaches after reading the whole
string.
Formal Process
Given:
·
A finite automaton defined as M =
(Q, Σ, δ, q0, F)
·
An input string w = a1a2a3…an,
where each ai is a symbol from the alphabet Σ
Steps:
i.
The automaton starts in the
initial state q0
ii.
For each symbol ai in the string w, the automaton moves to the next state
according to the transition function δ
iii.
Let qi be the current state at any
step
iv.
The next state is determined by δ(qi, ai)
v.
After reading the entire string,
the automaton ends in a state qf
Acceptance and Rejection
·
The string is accepted if the
final state qf belongs to the set of accept states F
·
The string is rejected if the
final state qf is not part of the accept states F
In Simple Words
·
If the automaton finishes reading
the string and is in an accepting state, the string is accepted
·
If the automaton ends in any other
state, the string is rejected
Example:
Strings that Start with ‘a’
Consider
a finite automaton that accepts strings starting with ‘a’ over the alphabet {a,
b}
The
automaton is defined as:
·
Q = {q0, q1, q2} (Set of states)
·
Σ = {a, b} (Input symbols)
·
q0 = Start state
·
F = {q1} (Accept state)
Transition Table
|
Current State |
Input ‘a’ |
Input ‘b’ |
|
q0 |
q1 |
q2 |
|
q1 |
q1 |
q1 |
|
q2 |
q2 |
q2 |
Processing Example Strings
String =
"a"
·
Start at q0
·
Read ‘a’ → move to q1
·
End in q1 → q1 is an
accepting state → String is accepted
String =
"ab"
·
Start at q0
·
Read ‘a’ → move to q1
·
Read ‘b’ → stay in q1
·
End in q1 → q1 is an
accepting state → String is accepted
String =
"b"
·
Start at q0
·
Read ‘b’ → move to q2
·
End in q2 → q2 is not an
accepting state → String is rejected
String =
"ba"
·
Start at q0
·
Read ‘b’ → move to q2
·
Read ‘a’ → stay in q2
·
End in q2 → q2 is not an
accepting state → String is rejected
Remember
The
entire string must be processed before deciding accept or reject
Only
ending in an accept state means the string is accepted
In the
case of a Non-Deterministic Finite Automaton (NFA), if there exists
at least one path leading to an accepting state, the string is accepted
Example 2:
Finite Automaton to Accept Strings Starting with ‘a’ over {a, b}
Informal Description:
The automaton checks if the first symbol of the input string is ‘a’.
·
If yes, it enters an accepting
state and stays there for the rest of the input.
·
If the first symbol is ‘b’, it
enters a rejecting state and stays there permanently.
Formal Definition:
The automaton is
defined as:
M = (Q, Σ, δ, q0, F)
Where:
·
Q = {q0, q1, q2} → Set of states
o q0 = initial state
o q1 = accepting state
o q2 = rejecting state
·
Σ = {a, b} → Input symbols (alphabet)
·
δ = Transition function defined as below
·
F = {q1} → Set of
accepting states
Transition Table:
|
Current State |
Input ‘a’ |
Input ‘b’ |
|
q0 |
q1 |
q2 |
|
q1 |
q1 |
q1 |
|
q2 |
q2 |
q2 |
States:
·
q0 (Initial State): The automaton starts here before reading any input.
·
q1 (Accept State): If the first symbol is ‘a’, the automaton moves here and stays,
accepting the string regardless of the remaining symbols.
·
q2 (Reject State): If the first symbol is ‘b’, the automaton moves here and stays,
rejecting the string regardless of the remaining symbols.
Alphabet:
Σ = {a, b} → The
only allowed symbols are ‘a’ and ‘b’.
Transition Function Details:
·
δ(q0, a) = q1 → From q0, reading ‘a’ moves to accept state q1
·
δ(q0, b) = q2 → From q0, reading ‘b’ moves to reject state q2
·
δ(q1, a) = q1 → In accept state q1, reading ‘a’ stays in q1
·
δ(q1, b) = q1 → In accept state q1, reading ‘b’ stays in q1
·
δ(q2, a) = q2 → In reject state q2, reading ‘a’ stays in q2
·
δ(q2, b) = q2 → In reject state q2, reading ‘b’ stays in q2
Start State:
The automaton starts in state q0.
Accept State:
The automaton accepts the string if it ends in state q1.
Examples of Strings and Their Processing:
String: "a"
Start at q0
Read ‘a’ → move to q1
End at q1 → Accepted
String: "ab"
Start at q0
Read ‘a’ → move to q1
Read ‘b’ → stay at q1
End at q1 → Accepted
String: "aba"
Start at q0
Read ‘a’ → move to q1
Read ‘b’ → stay at q1
Read ‘a’ → stay at q1
End at q1 → Accepted
String: "b"
Start at q0
Read ‘b’ → move to q2
End at q2 → Rejected
String: "ba"
Start at q0
Read ‘b’ → move to q2
Read ‘a’ → stay at q2
End at q2 → Rejected
