Unit 2: Finite Automata

Finite Automata, is a fundamental concept in computer science and automata theory. We

get the term "automaton" from the word "automatic".
Finite automata are abstract machines used to recognize patterns in input sequences,
forming the basis for understanding regular languages in computer science. They consist of
states, transitions, and input symbols, processing each symbol step-by-step. If the machine
ends in an accepting state after processing the input, it is accepted; otherwise, it is rejected.
Finite automata come in deterministic (DFA) and non-deterministic (NFA), both of which
can recognize the same set of regular languages. They are widely used in text processing,
compilers, and network protocols.

Features of Finite Automata

o Finite automata are used to recognize patterns.

o It takes the string of symbol as input and changes its state accordingly. When the
desired symbol is found, then the transition occurs.
o At the time of transition, the automata can either move to the next state or stay in the
same state.
o Finite automata have two states, Accept state or Reject state. When the input string
is processed successfully, and the automata reached its final state, then it will accept.
Formal Definition of FA
To represent the finite automata, we need 5 tuples −
M=(Q,Σ,δ,q0,F)
where −
Q − A finite, non-empty set of states.
Σ − A finite, non-empty set of input alphabets (symbols).
δ − The transition function, which maps into .
q0 − The initial state, which is an element of .
F − A subset of representing the set of final states.
Components of 5-Tuple
Following are the components of the 5-Tuple −
States (Q) − Q is a finite, non-empty set of states. Each state represents a unique condition
or configuration of the system.
Input Alphabets (Σ) − Σ is the finite, non-empty set of input symbols that the automaton
reads to determine state transitions.
Transition Function (δ) − δ is a set of functions that defines how the automaton transitions
from one state to another based on the current state and input symbol. It can be expressed
as: δ:Q×Σ→Q.
Initial State (q0) − q0 is the initial state from which the automaton starts its computation. It
belongs to the set.
Final States (F) − F is a subset of containing one or more final states. These states signify the
acceptance of the input string by the automaton.

Types of Finite Automata There are two types of finite automata:

1. Deterministic Fintie Automata (DFA)

2. Non-Deterministic Finite Automata (NFA)

1. Deterministic Finite Automata (DFA) A DFA is represented as {Q, Σ, q, F, δ}. In DFA, for
each input symbol, the machine transitions to one and only one state. DFA does not
allow any null transitions, meaning every state must have a transition defined for every
input symbol.

DFA consists of 5 tuples {Q, Σ, q, F, δ}.

Q : set of all states.
Σ : set of input symbols. ( Symbols which machine takes as input )
q : Initial state. ( Starting state of a machine )
F : set of final state.
δ : Transition Function, defined as δ : Q X Σ --> Q.
Example:
Construct a DFA that accepts all strings ending with ‘a’.
Given:
Σ = {a, b},
Q = {q0, q1},
F = {q1}
Fig 1. State Transition Diagram for DFA with Σ = {a, b}

State\Symbol a b

q0 q1 q0

q1 q1 q0

In this example, if the string ends in ‘a’, the machine reaches state q1, which is an accepting
state.
2) Non-Deterministic Finite Automata (NFA)
NFA is similar to DFA but includes the following features:
It can transition to multiple states for the same input.
It allows null (ϵ) moves, where the machine can change states without consuming any
input.
Example:
Construct an NFA that accepts strings ending in ‘a’.
Given:
Σ = {a, b},
Q = {q0, q1},
F = {q1}

Fig 2. State Transition Diagram for NFA with Σ = {a, b}

State Transition Table for above Automaton,
State\Symbol a b

q0 {q0,q1} q0

q1 φ φ

In an NFA, if any transition leads to an accepting state, the string is accepted.

Applications of Finite Automata
The following table summarizes the key applications of finite automata −
Application Area Description
Language Processing Used in email filters and smart assistants like Alexa, Siri,
and Google Assistant.
Compiler Translates high-level programming languages into
Construction machine code.
Computer Networks Underlies the design of network protocols such as HTTP
and HTTPS.
Video Games Manages game mechanics and AI, as seen in games like
Warcraft 3.
Digital Circuit Design Designs digital circuits in devices such as fans,
refrigerators, and washing machines.
Biomedical Problem Utilized in medical imaging technologies like X-ray
Solving diffraction and tomography.

Regular Expression

o The language accepted by finite automata can be easily described by simple expressions
called Regular Expressions. It is the most effective way to represent any language.
o The languages accepted by some regular expression are referred to as Regular languages.
o A regular expression can also be described as a sequence of pattern that defines a string.
o Regular expressions are used to match character combinations in strings. String searching
algorithm used this pattern to find the operations on a string.
For instance:

 In a regular expression, x* means zero or more occurrence of x. It can generate {e, x, xx,
xxx, xxxx, .....}
 In a regular expression, x+ means one or more occurrence of x. It can generate {x, xx, xxx,
xxxx, .....
Operations on Regular Language

The various operations on regular language are:

1. Union: If L and M are two regular languages then their union L U M is also a union.

L U M = {s | s is in L or s is in M}
2. Intersection: If L and M are two regular languages then their intersection is also an
intersection.

L ⋂ M = {st | s is in L and t is in M}
3. Kleen closure: If L is a regular language then its Kleen closure L1* will also be a regular
language.

L* = Zero or more occurrence of language L.

Example 1:
Write the regular expression for the language accepting all combinations of a's, over the set
∑ = {a}

Solution:

All combinations of a's means a may be zero, single, double and so on. If a is appearing zero
times, that means a null string. That is we expect the set of {ε, a, aa, aaa, ....}. So we give a
regular expression for this as:

R = a*
That is Kleen closure of a.

Example 2:
Write the regular expression for the language accepting all combinations of a's except the
null string, over the set ∑ = {a}

Solution:

The regular expression has to be built for the language

L = {a, aa, aaa, ....}

This set indicates that there is no null string. So we can denote regular expression as:

R = a+
Example 3:
Write the regular expression for the language accepting all the string containing any number
of a's and b's.
Solution:

The regular expression will be:

r.e. = (a + b)*
This will give the set as L = {ε, a, aa, b, bb, ab, ba, aba, bab, .....}, any combination of a and b.

The (a + b)* shows any combination with a and b even a null string.

Properties of Regular Expressions in TOC

All the properties held for any regular expressions R, E, F and can be verified by using
properties of languages and sets.
Additive (+) Properties
The additive properties of regular expressions are as follows −
R+E=E+R
R+∅=∅+R=R
R+R=R
(R + E) + F = R + (E + F)
Product (.) Properties
The product properties of regular expressions are as follows −
R∅ = ∅R = ∅
R∧ = ∧R = R
(RE)F = R(EF)
Distributive Properties
The distributive properties of regular expressions are as follows −
R(E + F) = RE + RF
(R + E)F = RF + EF
Closure Properties
The closure properties of regular expressions are as follows −
∅* = ∧ * = ∧
R* = R*R* = (R*)* = R + R*
R* = ∧ + RR* = (∧ + R)R*
RR* = R*R
R(ER)* = (RE)*R
(R + E)* = (R*E*)* = (R* + E*)* = R*(ER*)*
All the properties can be verified by using the properties of languages and sets.
Example:
Show that,
(∅ + a + b)* = a*(ba*)*
Using the properties above −
(∅ + a + b)* = (a + b)* (+ property)
= a*(ba*)* (closure property)
Example:
Show that,
∧ + ab + abab(ab)* = (ab)*
Using the properties above −
∧ + ab + abab(ab)* = ∧ + ab(∧ + ab(ab)*)
= ∧ + ab((ab)*) (using R* = ∧ + RR*)
= ∧ + ab(ab)*= (ab)* (using R* = ∧ + RR* again)

Deterministic Finite Automaton

DFA refers to deterministic finite automata. Deterministic refers to the uniqueness of the
computation. The finite automata are deterministic FA, if the machine reads an input string
one symbol at a time.
In DFA, there is only one path input from the current state to the next state. It does not
accept the null move, i.e. it cannot change state without any input. It can contain multiple
final states. It is used in Lexical Analysis in compilers.
In DFA, for each input symbol, one can determine the state to which the machine will
move. Hence, it is called Deterministic Automaton. As it has a finite number of states, the
machine is called Deterministic Finite Machine or Deterministic Finite Automaton.
Formal Definition of a DFA
A Deterministic Finite automata (DFA) is a collection of defined as a 5-tuples and is as
follows −
 M=(Q,Σ,δ,q0,F)
Where,
 Q is a finite set of states.
 ∑ is a finite set of symbols called the alphabet.
 δ is the transition function where δ: Q × ∑ → Q
 q0 is the initial state from where any input is processed (q0 ∈ Q).
 F is a set of final state/states of Q (F ⊆ Q).
Graphical Representation of a DFA
A DFA is represented by digraphs called state diagram.
 The vertices represent the states.
 The arcs labeled with an input alphabet show the transitions.
 The initial state is denoted by an empty single incoming arc.
 The final state is indicated by double circles.
Example 1
Let a deterministic finite automaton be →
Q = {a, b, c},
∑ = {0, 1},
q0 = {a},
F = {c}, and
Transition Table
Transition function δ as shown by the following table −

Present Next State for Next State for

State Input 0 Input 1

a a b

b c a

c b c

Its graphical representation would be as follows −

Example 2
Minimize the following DFA

Solution
Make a transition Table.

π0={{5},{1,2,3,4}}π0={{5},{1,2,3,4}}
For input a, on {1,,2,3,4}of π0 For input a, on {1,,2,3,4}of π0

or input b, on {1, 2, 3, 4} of π0
 ∴{1,2,3,4} will be split into {1,3}and{2,4}∴{1,2,3,4} will be split into {1,3}and{2,4}
∴π1={{5},{1,3},{2,4}}∴π1={{5},{1,3},{2,4}}
For input symbol a on {1, 3} of π1

Similarly for input symbol a on {2, 4} of π1

For input symbol b on {1, 3} of π1

Similarly for input symbol b on {2, 4} of π1

Subset in π1 i.e., {1, 3} & {2, 4} will not be splitted.

πfinal={{5},{1,3},{2,4}}πfinal={{5},{1,3},{2,4}}
There will be 3 states of DFA.
{5},{1,3}and{2,4}{5},{1,3}and{2,4}
Minimized DFA will be −
Application of Deterministic Finite Automata (DFA)
The different applications of deterministic finite automata are as follows −
 Protocol analysis text parsing.
 Video game character behavior.
 Security analysis.
 CPU control units.
 Natural language processing Speech recognition, etc.