S.Venkat, Asst.

Professor @CSE 2021

FORMAL LANGUAGE AND AUTOMATA THEORY

UNIT-1

• Why Study Automata Theory?

• The Central Concepts of Automata Theory
• Automation Finite Automation Transit ion Systems,
• Acceptance of a String by a Finite Automation,
• DFA, Design of DFAs, NFA, Design of NFA
• Equivalence of DFA and NFA Conversion of NFA into DFA ,
• Finite Automata with E-Transition,
• Minimization of Finite Automata ,
• Mealy and Moore Machines ,
• Applications and Limitation of Finite Automata.
• Differences between DFA and NFA ,
• Differences between Mealy and Moore Machines.
Why Study Automata Theory?
There are several reasons why the study of automata and complexity is an important part of
the core of Computer Science.
Computer science can be divided into two main branches.
1. “Applied Computer Science” which is concerned with the design and implementation of
computer systems, with a special focus on software.
2. “Theoretical Computer Science” or “Theory of computation” which is concerned with
mathematical study of computation.

The central areas of theory of computation are

I. Automata theory
II. Computational theory
III. Complexity theory

Computational theory and Complexity theory:

The theories of computability and complexity are closely related. In complexity theory, the
objective is to classify problems as easy ones and hard ones; whereas in computability theory,
the classification of problems is by those that are solvable and those that are not.

Computational Problem:

“Computational Problem” means any problem that can be modeled to be solved by a

computer.

Computation:

“Computation” can be defined as finding a solution to a problem from the given inputs by
means of an algorithm.

Automata theory:
It deals with the formal definitions and properties of mathematical models of computation.
These models play a role in several applied areas of computer science. One model, called the
finite automaton, is used in text processing, compilers, and hardware design. Another model,
called the context-free grammar, is used in programming languages and artificial intelligence.

Finite automaton is a useful model for

1. Software for designing and checking the behavior of digital circuits (hardware
design).
2. The "lexical analyzer" of a typical compiler, that is, the compiler component that
breaks the input text into logical units, such as identifiers, keywords, and punctuation
(compilers).
3. Software for scanning large bodies of text, such as collections of Web pages, to find
occurrences of words, phrases, or other patterns (text processing).
The theories of computability and complexity require a precise definition of a computer.
Automata theory allows practice with formal definitions of computation.
The Central Concepts of Automata Theory:
Symbol: Symbol is any character which is meaningful or meaningless.
Example: A,B,C,….,Z
a,b,c,…z
0,1,2,…9
∑, λ, δ, π…
Alphabet: An alphabet is a finite, and non empty set of symbols. It is denoted by ∑.
Common alphabets include:
Example: 1. ∑= {0, 1}, is the binary alphabet.
2. ∑ = {a, b,…, z}, is lower-case English alphabet.
3. ∑ = {0,1,2,…9}, is decimal number alphabet.
String: A string is a finite sequence of symbols from some alphabet.
Example: ∑= {0, 1}, is the binary alphabet.
Strings are 00,01,10,11, ɛ …
Empty String: The empty string is the string with zero occurrences of symbols. It is denoted
by ɛ.
Length of a string: the length of a string is "the number of symbols" in the string. length of a
string w is denoted by |w|. length of empty string is 0.
Example: w=sri, |w|= 3
Powers of an alphabet (set of strings of length k): If ∑ is an alphabet, then set of all strings
of a certain length k are denoted by ∑k.
Example: if ∑= {0, 1}, then ∑0 = {ɛ} – strings of length 0,
∑1={0,1}– strings of length 1,
∑2={00,01,10,11}– strings of length 2,…
Prefix of a string: prefix of a string is formed by removing zero or more tailing symbols of
the string. For a string of length n, number of prefixes= n+1.
Example: w= sri, |w|= 3 prefix= sri, sr, s, ɛ.

Proper prefix: prefix of a string other than itself is called proper prefix.
Example: w=sri, |w|=3 proper prefix= sr, s, ɛ.
suffix of a string: suffix of a string is formed by removing zero or more leading symbols of
the string. For a string of length n, number of suffixes= n+1.
Example: w=sri, suffix=sri,ri,i,ɛ.
Proper suffix: suffix of a string other than itself is called proper suffix.
Example: w=sri, proper suffix= ri,i,ɛ.
substring of a string: substring of a string is formed by removing either prefix or suffix or
both from a string excluding ɛ. For a string of length n, number of substrings= n*(n+1)/2.
Example: w=sri, substring= sri, sr,s,ri,i,r
Language: language is a collection of strings formed from a particular alphabet.

Example: if ∑= {0, 1}, then the language of all strings consisting of n 0' s followed by n l' s,
for some n≥0 is L= {ɛ, 01,0011,000111,. .}.
Operations on strings:
1. Concatenation of a string
2. Kleene closure of a string
3. Positive closure of a string
4. Reverse of a string
Concatenation of a string: concatenation of a string is obtained by appending second string
at the end of first string. If w1 and w2 are strings, then w1.w2 or w1w2 denotes the
concatenation of w1 and w2.

Example: w1=sri , w2=lakshmi , then w1.w2= srilakshmi

length of concatenated string is |w1.w2|=|w1|+|w2|.
Example: w1=sri w2=lakshmi w1.w2=srilakshmi |w1.w2|=|w1|+|w2|=3+7=10
Kleene closure of a string: Set of all strings over an alphabet ∑ is known as kleene closure.
It is denoted by ∑*.
∑* = ∑0 ∪ ∑1 ∪∑2 ∪ ...

Example: if ∑= {0, 1}, then ∑0 = {ɛ} – strings of length 0,

∑1={0,1}– strings of length 1,
∑2={00,01,10,11}– strings of length 2,…

∑* = ∑0 ∪ ∑1 ∪∑2 ∪ ... ={ ɛ, 0, 1, 00 ,01, 10, 11, …}

Positive closure of a string: Set of all strings over an alphabet ∑ excluding the empty string
is known as positive closure. It is denoted by ∑+.
∑+ = ∑1 ∪∑2 ∪ ∑3 ∪… or ∑+ = ∑*-{ɛ}
Example: if ∑= {0, 1}, then ∑0 = {ɛ} – strings of length 0,
∑1={0,1}– strings of length 1,
∑2={00,01,10,11}– strings of length 2,…

∑* = ∑0 ∪ ∑1 ∪∑2 ∪ ... ={ ɛ, 0, 1, 00 ,01, 10, 11, …}

∑+ = ∑*-{ɛ} = { 0, 1, 00 ,01, 10, 11, …}
Reverse of a string: Reverse of a string is obtained by reading the string from back to front.
If w is a string, then reverse of a string w is denoted by wR.
Example: w=sri then wR=irs

Operations on languages:
1. Union of a language
2. Intersection of a language
3. Difference of a language
4. Complement of a language
5. Concatenation of a language
6. Kleene closure of a language
7. Positive closure of a language
Union of a language: Union of two languages is defined as collection of strings from L1 as
well as from L2. It is denoted as L1∪L2.

L1∪L2={w| w in L1 or w in L2}

Example: if L1= {0,1} and L2= {00,11} then L1∪L2={0,1,00,11}

Intersection of a language: Intersection of two languages is defined as collection of strings
common in both L1 as well as L2. It is denoted as L1∩L2.

L1∩L2={w| w in L1 and w in L2}

Example: if L1= {00,1} and L2= {00,11} then L1∩L2={00}

Difference of a language: Difference of two languages is defined as collection of strings

from L1 that are not in L2. It is denoted as L1−L2.

L1−L2={w| w in L1 and not in L2}

Example: if L1= {00,1} and L2= {00,11} then L1-L2={1}
Complement of a language: Complement of a language is defined as language consisting of
all the strings that are not in language L. It is denoted as LC.

LC =∑* −L
Example: if L= {set of strings that starts with 010} over ∑= {0, 1}
then LC =∑* −L ={set of all strings} −{set of strings that starts with 010}
= { set of strings that does not starts with 010}
Concatenation of a language: Concatenation of a two languages is obtained by appending
every string in second language at the end of every string in first language. If L1 and L2 are
two languages, then L1.L2 or L1L2 denotes the concatenation of L1 and L2.

L1.L2={w| w1 in L1 and w2 in L2}

Example: if ∑= {0, 1}, then the language of all strings consisting of n 0' s followed by n l' s,
for some n≥0 is L1= {ɛ, 01,0011,000111,. .}.
if ∑= {0, 1}, then the language of all strings consisting of an equal number of 0's and l's is
L2= {ɛ, 01, 10, 0011, 0101, 1001, .. .}.
L1.L2={ ɛ. ɛ , ɛ. 01, ɛ. 10, ɛ. 0011, ɛ. 0101, ɛ. 1001,…,0110,010011,010101,…}
= {ɛ, 01, 10, 0011, 0101, 1001, .. ., 0101,010011,010101…}
Kleene closure of a language: If L is a language, Set of all strings formed by concatenation
of zero or more strings of the language is known as kleene closure. It is denoted by L*.
Li = Li-1.L, i≥1
L* = L0 ∪ L1 ∪L2 ∪ ...
Example: if ∑= {0, 1}, then language containing strings of length 1 is L= {0, 1},
then L0 = {ɛ}
L1= L0.L ={ɛ}.{0,1}={0,1}
L2= L1.L = {0,1}.{0,1}={00,01,10,11}
L* = L0 ∪ L1 ∪L2 ∪ ... ={ ɛ, 0, 1, 00 ,01, 10, 11, …}

Positive closure of a language: If L is a language, Set of all strings formed by concatenation

of one or more strings of the language is known as positive closure. It is denoted by L+.
L+ = L1 ∪L2 ∪ L3 ∪… or L+ = L*-{ɛ}
Example: if ∑= {0, 1}, }, then language containing strings of length 1 is L= {0, 1}, then L0 = {ɛ}
L1= L0.L ={ɛ} {0,1}={0,1}
L2= L1.L = {0,1}{0,1}={00,01,10,11}
L* = L0 ∪ L1 ∪L2 ∪ ... ={ ɛ, 0, 1, 00 ,01, 10, 11, …}
L+ = L*-{ɛ} = { 0, 1, 00 ,01, 10, 11, …}
Automata: Automata is plural for the term “Automaton”. An Automaton is defined as a
system where information is transmitted and used for performing some internal operations
without direct participation of human.

Finite State Machine/ Finite Automata: “Finite State Machine” is a model of computation
which is used to simulate the behavior of a machine or a system.

Model of Finite Automata: It includes

1. Components of Finite State Machine

2. Elements of Finite State Machine
3. Working of Finite State Machine
4. Mathematical representation of Finite State Machine

1.Components of Finite State Machine: Finite State Machine consists of 3 components.

They are 1. Input tape
2. Read head and
3. Finite Control

Input tape:
It is used to store the input string that is to be processed by Finite State Machine. The input is
finite and taken from a set of input alphabets ∑.

Read head:
It is used to read one symbol at a time from input tape and moves from left to right.
Initially it points to the leftmost symbol on the tape and it is controlled by “Finite control”.
Finite Control:

Finite control contains a set of states which are connected by transitions. In finite control, it is
decided that “machine is in this state and it is getting this input, so it will go to this state”.

2. Elements of Finite State Machine: The main elements of Finite State Machine are
1. State
2. Rules
3. State Transition
4. Input Events
1) State :-
This element defines the behavior of the system and generate action to be performed. There
are different types of states. They are a. Start state
b. Next state
c. Accepting state
d. Dead state
e. Inaccessible state
f. Universal State
g. Existential State
Types of states:
a. Start state: State which is used to start processing of input string in finite state
machine is called as “start state” or “initial state”.
b. Next state: State which is defined by the transition function of finite state machine for
current state qi and input symbol x is called as “next state”.
𝛿(𝑞𝑖 , 𝑥) → 𝑞
c. Accepting state: Once entire string is processed, state which leads to acceptance of
string is called as “Accepting state” or “final state”.
d. Dead state: A non final state of finite state machine whose transitions on every input
symbol terminates on itself is called as “dead state”.
𝑞 ∉ 𝐹 𝑎𝑛𝑑 𝛿(𝑞𝑖 , Σ) → qi
e. Inaccessible state: State which can never be reached from initial state is called
“inaccessible state” or “useless state”.
f. Equivalent state: Two states are “equivalent” or “indistinguishable”, if both
produces final states or if both produces non final states on applying same input
symbol.
𝛿(𝑞𝑖 , 𝑥) ∈ 𝐹 → 𝛿(𝑞𝑗 , 𝑥) ∈ 𝐹
𝛿(𝑞𝑖 , 𝑥) ∈ 𝑁𝐹 → 𝛿(𝑞𝑗 , 𝑥) ∈ 𝑁F
g. Distinguishable state: Two states are “not equivalent” or “distinguishable”, if both
produces final states or if both produces non final states on applying same input
symbol.
𝛿(𝑞𝑖 , 𝑥) ∈ 𝐹 → 𝛿(𝑞𝑗 , 𝑥) ∈ 𝑁𝐹
𝛿(𝑞𝑖 , 𝑥) ∈ 𝑁𝐹 → 𝛿(𝑞𝑗 , 𝑥) ∈ F

2. Rules:
This element defines the conditions that are to be satisfied for enabling state transition.

3. State transition:
This element defines the change in state. i,e., moving from one state to another state is known
as transition. Transitions are represented in 3 ways.
They are 1. Transition diagram
2. Transition table
3. Transition function
Types of transition:
I. Transition diagram/ Transition graph/ Transition system:
A diagrammatical representation of states and transitions is called as transition
diagram. In transition diagram, circles are used to represent states and directed arrows
are used to represent transitions between states.

For a finite state machine, transition diagram or transition graph or a transition

system is formally defined as a directed labeled graph where each vertex is a state,
and directed edge is a transition between two states and edges are labeled with
input/output.
Note: For DFA, NFA, and Moore machine, only input is labeled on each edge, where
as in mealy machine, both input and output are labeled on each edge.

Representations:

Start state

Final state
Other states

initial and final states are same

transition between two states

transition between two states with input and output

II. Transition table: Tabular representation of states and transitions is called as

transition table. In transition table, rows are used to represent states and columns are
used to represent input symbols and entry in table represents the next state based on
current state and input symbol.
In this representation start state is marked by an arrow (→) and final state is
marked by an asterisk (*) or enclosed within a single circle (①).
III. Transition function: Mathematical representation of states and transitions is called as
transition function. It is denoted by 𝜹. There are two types of transition function
depending on number of arguments.
They are 1. Direct transition function
2. Indirect transition function.

Direct transition function: When the input is a symbol, it is known as direct

transition function. It is denoted by 𝜹(𝒒𝒊 , 𝒙) = 𝒒j where
𝒒𝒊 is used to represent current state
𝒙 is used to represent input symbol and
𝒒j represents the next state based on current state and input symbol.
Note: 𝜹(𝒒𝒊 , 𝜺) = 𝒒𝒊 , i.e state changes only on applying an input symbol.

Indirect transition function:

When the input is a string xw , it is known as indirect transition function. It is denoted
by 𝜹(𝒒𝒊 , 𝒙𝒘) ⊢ 𝜹(𝜹(𝒒𝒊 , 𝒙),𝒘) where
𝒒𝒊 is used to represent current state
𝒙 is used to represent current input symbol and
𝜹(𝒒𝒊 , 𝒙) represents the next state based on qi and x and
𝒘 represents the remaining input string.
4. Input events:
This element is used to evaluate rules and lead to transition. These may be generated
internally or externally.

3. Working of finite state machine :

Computation begins in start state with input string in input tape. The read head scans the
input from input tape and sends it to finite control.

Based on current state and input symbol of finite state machine, next state will be determined.

After processing the entire string, if the finite control enters into one of the final states, FSM
declares that string is accepted and recognizes that string belongs to the given language.,
otherwise it declares that string doesn’t belongs to the given language.

4. Mathematical representation of Finite State Machine/Finite Automata:

Finite Automata is formally defined as 5-tuple 𝑴 = (𝑸, 𝚺, 𝜹, 𝒒𝟎, 𝑭) where

𝑀 = 𝐹𝑖𝑛𝑖𝑡𝑒 𝑆𝑡𝑎𝑡𝑒 𝑀𝑎𝑐ℎ𝑖𝑛𝑒
𝑄 − 𝑓𝑖𝑛𝑖𝑡𝑒 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑠𝑡𝑎𝑡𝑒𝑠
Σ − 𝑖𝑛𝑝𝑢𝑡 𝑎𝑙𝑝ℎ𝑎𝑏𝑒𝑡 𝑜𝑟 𝑠𝑒𝑡 𝑜𝑓 𝑖𝑛𝑝𝑢𝑡 𝑠𝑦𝑚𝑏𝑜𝑙𝑠
𝛿 − 𝑡𝑟𝑎𝑛𝑠𝑖𝑡𝑖𝑜𝑛 𝑓𝑢𝑛𝑐𝑡𝑖𝑜𝑛 𝑑𝑒𝑓𝑖𝑛𝑒𝑑 𝑏𝑦 𝛿:𝑄𝑋Σ → Q
𝑞0 − 𝑠𝑡𝑎𝑟𝑡 𝑠𝑡𝑎𝑡𝑒 𝑞0 ∈ 𝑄
𝐹 − 𝑠𝑒𝑡 𝑜𝑓 𝑓𝑖𝑛𝑎𝑙 𝑠𝑡𝑎𝑡𝑒𝑠 𝐹 ⊆ Q

Transition System:
A transition system is formally defined as a directed labeled graph where each vertex is a
state, and directed edge is a transition between two states and edges are labeled with
input/output.
A transition system is a 5-tuple (𝑸, 𝚺, 𝜹, 𝒒𝟎,𝑭) where
𝑄 − 𝑓𝑖𝑛𝑖𝑡𝑒 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑠𝑡𝑎𝑡𝑒𝑠
Σ − 𝑖𝑛𝑝𝑢𝑡 𝑎𝑙𝑝ℎ𝑎𝑏𝑒𝑡 𝑜𝑟 𝑠𝑒𝑡 𝑜𝑓 𝑖𝑛𝑝𝑢𝑡 𝑠𝑦𝑚𝑏𝑜𝑙𝑠
𝛿 − 𝑡𝑟𝑎𝑛𝑠𝑖𝑡𝑖𝑜𝑛 𝑓𝑢𝑛𝑐𝑡𝑖𝑜𝑛 𝑑𝑒𝑓𝑖𝑛𝑒𝑑 𝑏𝑦 𝛿:𝑄𝑋Σ∗→𝑄
𝑞0 − 𝑠𝑡𝑎𝑟𝑡 𝑠𝑡𝑎𝑡𝑒 𝑞0 ∈ 𝑄
𝐹 − 𝑠𝑒𝑡 𝑜𝑓 𝑓𝑖𝑛𝑎𝑙 𝑠𝑡𝑎𝑡𝑒𝑠 𝐹 ⊆ 𝑄 i.e if (𝑞0, w. 𝑞2) is in 𝜹.
it means that the graph starts at the vertex 𝑞0, goes along a set of edges, and reaches the vertex
𝑞2 . The concatenation of the label of all the edges thus encountered is w.

Acceptability of a string by finite automata:

i.e., A string w is accepted by finite automata M = (𝑸, 𝚺, 𝜹, 𝒒𝟎,𝑭) if 𝛿(𝑞0, 𝑤) = 𝑞f for some
𝑞𝑓 𝜖 F. This is basically acceptability of a string by the final state.
Types of Finite Automata: Finite Automata can be classified into 2 types.
They are 1. Finite Automata without output (recognizers)
2. Finite Automata with output(tranducers)
1. Finite Automata without output are classified into 3 types. They are
Deterministic Finite Automata (DFA)
Non Deterministic Finite Automata (NFA)
Non Deterministic Finite Automata with Epsilon transitions (NFA-ℇ)
Minimized DFA
2. Finite Automata with output are classified into 2 types. They are
Moore Machine
Mealy Machine

1. Finite Automata without output (RECOGNIZERS):

Deterministic Finite Automata (DFA)

Definition: Deterministic Finite Automata can be defined as “it is a finite automata in which all
the moves of a machine can be uniquely determined by using current state and input symbol.
i.e., For the given input symbol, there will be only one transition from the current state.

Mathematical representation of DFA:

DFA is formally defined as 5-tuple 𝑴 = (𝑸, 𝚺, 𝜹, 𝒒𝟎, 𝑭) where

𝑀 = 𝐹𝑖𝑛𝑖𝑡𝑒 𝑆𝑡𝑎𝑡𝑒 𝑀𝑎𝑐ℎ𝑖𝑛𝑒
𝑄 − 𝑓𝑖𝑛𝑖𝑡𝑒 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑠𝑡𝑎𝑡𝑒𝑠
Σ − 𝑖𝑛𝑝𝑢𝑡 𝑎𝑙𝑝ℎ𝑎𝑏𝑒𝑡 𝑜𝑟 𝑠𝑒𝑡 𝑜𝑓 𝑖𝑛𝑝𝑢𝑡 𝑠𝑦𝑚𝑏𝑜𝑙𝑠
𝛿 − 𝑡𝑟𝑎𝑛𝑠𝑖𝑡𝑖𝑜𝑛 𝑓𝑢𝑛𝑐𝑡𝑖𝑜𝑛 𝑑𝑒𝑓𝑖𝑛𝑒𝑑 𝑏𝑦 𝛿:𝑄𝑋Σ → Q
𝑞0 − 𝑠𝑡𝑎𝑟𝑡 𝑠𝑡𝑎𝑡𝑒 ., 𝑞0 ∈ 𝑄
𝐹 − 𝑠𝑒𝑡 𝑜𝑓 𝑓𝑖𝑛𝑎𝑙 𝑠𝑡𝑎𝑡𝑒𝑠 𝐹 ⊆ Q

Working of DFA:

• Initially DFA is assumed to be in its start state q0 with its read head on leftmost
symbol of input string in input tape.
• The read head scans the input from input tape and sends it to finite control.
• Based on current state and input symbol of finite state machine, next state will be
determined by finite control.
• During each move, read head moves one position to the right.
• After processing the entire string, if the DFA enters into one of the final states, the
string is accepted, otherwise the string is rejected.
Design of DFAs:

1. Write the strings in the given language using the given input alphabet ∑.
2. Design DFA for the minimum string in the language.
3. At each state, for the input symbol which has no transition, put a loop over that
particular state with that input symbol.
4. If the language is satisfied for that loop on that state, then check for next state.
Otherwise, put the transition for the previous state with that input symbol.
5. If then also, it is not satisfied, then put the transition for the previous state with that
input symbol.
6. If it is a start state, include a new state called as dead state.
7. Repeat the steps 2-5 until each and every state in DFA is having a transition with each
and every input symbol.

Non- Deterministic Finite Automata (NDFA/NFA)

Definition: Non Deterministic Finite Automata can be defined as “it is a finite automata in
which some of the moves of a machine cannot be uniquely determined by using current state
and input symbol. i.e., For the given input symbol, there will be more than one transition from
the current state.

Mathematical representation of NFA:

NFA is formally defined as 5-tuple 𝑴 = (𝑸, 𝚺, 𝜹, 𝒒𝟎, 𝑭) where

𝑀 = 𝐹𝑖𝑛𝑖𝑡𝑒 𝑆𝑡𝑎𝑡𝑒 𝑀𝑎𝑐ℎ𝑖𝑛𝑒
𝑄 − 𝑓𝑖𝑛𝑖𝑡𝑒 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑠𝑡𝑎𝑡𝑒𝑠
Σ − 𝑖𝑛𝑝𝑢𝑡 𝑎𝑙𝑝ℎ𝑎𝑏𝑒𝑡 𝑜𝑟 𝑠𝑒𝑡 𝑜𝑓 𝑖𝑛𝑝𝑢𝑡 𝑠𝑦𝑚𝑏𝑜𝑙𝑠
𝛿 − 𝑡𝑟𝑎𝑛𝑠𝑖𝑡𝑖𝑜𝑛 𝑓𝑢𝑛𝑐𝑡𝑖𝑜𝑛 𝑑𝑒𝑓𝑖𝑛𝑒𝑑 𝑏𝑦 𝛿: 𝑄𝑋Σ → 2Q ,2Q ⊆ 𝑄
𝑞0 − 𝑠𝑡𝑎𝑟𝑡 𝑠𝑡𝑎𝑡𝑒 𝑞0 ∈ 𝑄
𝐹 − 𝑠𝑒𝑡 𝑜𝑓 𝑓𝑖𝑛𝑎𝑙 𝑠𝑡𝑎𝑡𝑒𝑠 𝐹 ⊆ 𝑄
Working of NFA:

• Initially NFA is assumed to be in its start state q0 with its read head on leftmost
symbol of input string in input tape.
• The read head scans the input from input tape and sends it to finite control.
• Based on current state and input symbol of finite state machine, several choices may
exist for the next state. Then the machine chooses one of them and continues.
• If the next input symbol matches, it continues. Otherwise, it chooses another way.
• During each move, read head moves one position to the right.
• After processing the entire string, if the NFA enters into one of the final states, the
string is accepted, otherwise the string is rejected.
Design of NFAs:

1. Write the strings in the given language using the given input alphabet ∑.
2. Design NFA for the minimum string in the language.
3. Put the transition with the input symbol wherever necessary, such that all strings of
given language are accepted by NFA.

Equivalence of DFA and DFA: Two DFAs M1 and M2 are said to be equivalent, if the
language accepted by 2 DFAs is same irrespective of number of states. i.e., if L(M1)=L(M2),
then M1 and M2 are equivalent.
Procedure:

1. Draw transition table format with input symbols and pair of states. Each pair of states
contains state from M1 and state from M2.
2. Initially take start states of M1 and M2 as a pair and generate new pair of states with
the input symbols of DFA.
3. During the process of generating new pair of states, if a pair of type (F,NF) or (NF,F)
is generated, then immediately stop the process and conclude that given DFAs are not
equivalent.
4. During the process of generating pairs of states, if a pair of type (F,F) or (NF,NF) is
generated, then repeat the process until no new pair of states are found and conclude
that given DFAs are equivalent.

Equivalence of DFA and NFA/ Conversion from NFA to DFA:

1. Draw the transition table for the given NFA.

2. Draw the transition table format for the required DFA with the input symbols in the
given DFA having only initial state.
3. The start state of DFA is the start state of given NFA.
4. If over an input symbol in DFA, a new state is obtained, then make that state as the
stat in DFA.
5. Repeat step4 until no new state is found.
6. The final states of DFA are those states that contain the final states of NFA.

NFA With Epsilon Transitions(NFA-ɛ / ɛ-NFA)

Definition: Non Deterministic Finite Automata with epsilon transitions can be defined as “it is a
non deterministic finite automata in which some of the transitions of a machine can be made
without reading any input symbol. i.e., without any input symbol (ɛ), there will be a transition
from the current state.

ɛ - transitions: ɛ - transitions are the transitions by using which NFA can change its state
without reading any input symbol.
ɛ - closure: ɛ - closure of a state is set of all the states reachable from that state by using only ɛ -
transitions including itself.

ɛ-closure(q0)={q0,q1,q2} for
Mathematical representation of NFA-ɛ:

NFA-ɛ is formally defined as 5-tuple 𝑴 = (𝑸, 𝚺, 𝜹, 𝒒𝟎, 𝑭) where

𝑀 = 𝐹𝑖𝑛𝑖𝑡𝑒 𝑆𝑡𝑎𝑡𝑒 𝑀𝑎𝑐ℎ𝑖𝑛𝑒
𝑄 − 𝑓𝑖𝑛𝑖𝑡𝑒 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑠𝑡𝑎𝑡𝑒𝑠
Σ − 𝑖𝑛𝑝𝑢𝑡 𝑎𝑙𝑝ℎ𝑎𝑏𝑒𝑡 𝑜𝑟 𝑠𝑒𝑡 𝑜𝑓 𝑖𝑛𝑝𝑢𝑡 𝑠𝑦𝑚𝑏𝑜𝑙𝑠
𝛿 − 𝑡𝑟𝑎𝑛𝑠𝑖𝑡𝑖𝑜𝑛 𝑓𝑢𝑛𝑐𝑡𝑖𝑜𝑛 𝑑𝑒𝑓𝑖𝑛𝑒𝑑 𝑏𝑦 𝛿: 𝑄𝑋Σ ∪ {ε} → 2Q ,2Q ⊆ 𝑄
𝑞0 − 𝑠𝑡𝑎𝑟𝑡 𝑠𝑡𝑎𝑡𝑒 𝑞0 ∈ 𝑄
𝐹 − 𝑠𝑒𝑡 𝑜𝑓 𝑓𝑖𝑛𝑎𝑙 𝑠𝑡𝑎𝑡𝑒𝑠 𝐹 ⊆ 𝑄
Working of NFA-ɛ:

• Initially NFA-ɛ is assumed to be in its start state q0 with its read head on leftmost
symbol of input string in input tape.
• The read head scans the input from input tape and sends it to finite control.
• Based on current state and input symbol of finite state machine, several choices may
exist for the next state. Then the machine chooses one of them and continues.
• If there is no input symbol, then using epsilon transition, it moves to next state and
continues. If the next input symbol matches, it continues. Otherwise, it chooses
another way.
• During each move, read head moves one position to the right.
• After processing the entire string, if the NFA-ɛ enters into one of the final states, the
string is accepted, otherwise the string is rejected.

Design of NFA-ɛ:

1. Write the strings in the given language using the given input alphabet ∑.
2. Design NFA- ɛ for the minimum string in the language.
3. Put the transition with the ɛ symbol wherever necessary, such that all strings of given
language are accepted by NFA-ɛ.

Equivalence of NFA-ɛ and NFA / Conversion from NFA-ɛ to NFA:

1. Find ɛ - closures of all the states in given NFA- ɛ.
2. Find transitions for NFA 𝜹′ with every state and every input symbol of given NFA- ɛ using
𝜹′(𝒒𝒑, 𝒊) = 𝜺 − 𝒄𝒍𝒐𝒔𝒖𝒓𝒆 (𝜹(𝜺 − 𝒄𝒍𝒐𝒔𝒖𝒓𝒆( 𝒒𝒑), 𝒊)
3. Draw the transition diagram based on transitions obtained.
4. The start state of NFA is the start state of given NFA- ɛ.
5. The final states of NFA are the final states of NFA- ɛ.
Minimized Deterministic Finite Automata (Minimized DFA):
Definition: DFA with number of states as minimum as possible is called as “Minimized Finite
Automata”.

Procedure to minimize DFA: There are 2 ways to minimize DFA. They are

1. Equivalence method
2. Myhill-Nerode theorem
1. Equivalence method:

Def. of k-equivalent: Two states are said to be “k-equivalent” (k≥0) , if both produces final
states or if both produces non final states on applying same input of length k or less.

Def. of K=0, 0-equivalent: The only string with length “0” is ɛ. If ɛ is applied on any state, it
cannot reach a final state, but if ɛ is applied on any state, it reaches a final state, since the ɛ- closure
of any state includes the state itself.

Therefore at level “0”, behavior of final states differ from non final states. so, partition the states
into 2 groups, final and non final. It is denoted by 𝜋0.

Def. of K=1, 1-equivalent: It is denoted by 𝜋1. Equivalence at level 1 can exist if and only if there
is equivalence at level “0”. Therefore here equivalence is to be checked among the states that were
equivalent in level 0 (subsets of 𝜋0). States having the same behavior will be grouped.

Procedure:

1. Write the set of states Q in the given DFA.

2. Find 0-equivalence (𝜋 0): Partition Q into 2 groups, I - Final states ‘F’ and II - Non- Final
states ‘NF’. 𝜋0 = (𝐼,𝐼𝐼) = (𝐹, 𝑄 − 𝐹)
3. Find 1-equivalence (𝜋 1): check equivalence on subsets (groups) of 𝜋0 and perform
partition on subsets of 𝜋0 F, NF to find new groups.
𝜋 1 = (I,III,IV.. )
• If the group of 𝜋0 contains a single state, then further it cannot be partitioned.
• For each group, write the transition table with input symbols on row side and states on
column side.
• Rewrite the transition table by replacing the transition with its group number that it falls
into.
• For any input symbol, if transition is made to same subset of 𝜋0, then it cannot be
partitioned.
• For any input symbol, if transition is made to different subset of 𝜋0, then subset is again
partitioned.
4. Similarly find 2-equivalence (𝜋 2) and so on until 𝜋 n−1 = 𝜋n.
5. For any input symbol, if no partitions are made on subsets of 𝜋n, then that states are
indistinguishable and these groups are the states of modified DFA.
6. Draw transition table for the minimized DFA with modified states on row side and input
symbols on column side and generate the transitions.
7. Draw transition diagram based on transition table obtained in step 6. This is the required
minimized DFA.
8. Remove any useless states to obtain optimized DFA.
2. Myhill-Nerode theorem:

1. Draw transition table for given DFA.

2. Write the set of states Q in the given DFA and partition Q into 2 groups, Final states ‘F’
and Non-Final states ‘NF’.
3. Make two dimensional matrix labeled by states of DFA at left side and bottom.
4. The major diagonal and upper triangular matrix is marked with dashes.
5. Write the combinations by attaching final states to non final states and put X in that
combinations in the matrix.
6. Write the combinations by attaching non final states to non final states.
7. For each pair of states, draw the transition table with input symbols on row side and
states on column side and generate new pair of states.
8. If any of new pair of states generated is either X (or) x, then the pair taken is marked
with x. Otherwise pair is marked with zero ‘0’.
9. Write the modified matrix.
10. The combinations of entries 0 are the states of minimized DFA.
11. Draw transition table for the minimized DFA with modified states on row side and input
symbols on column side and generate the transitions.
12. Draw transition diagram based on transition table obtained in step 6. This is the required
minimized DFA.
13. Remove any useless states to obtain optimized DFA.

2. Finite Automata with output (TRANDUCERS):

MOORE MACHINE:
Definition: It was proposed by Edward F. Moore. Moore machine is a finite automata with output
where output depends on present state only. In this machine, states are labeled with state name and
output.
Mathematical representation of Moore machine:
Moore machine is formally defined as 6-tuple 𝑴 = (𝑸, 𝚺, 𝚫, 𝜹, 𝝀, 𝒒𝟎) where
𝑀 = 𝑀𝑜𝑜𝑟𝑒 𝑀𝑎𝑐ℎ𝑖𝑛𝑒
𝑄 − 𝑓𝑖𝑛𝑖𝑡𝑒 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑠𝑡𝑎𝑡𝑒𝑠
Σ − 𝑖𝑛𝑝𝑢𝑡 𝑎𝑙𝑝ℎ𝑎𝑏𝑒𝑡 𝑜𝑟 𝑠𝑒𝑡 𝑜𝑓 𝑖𝑛𝑝𝑢𝑡 𝑠𝑦𝑚𝑏𝑜𝑙𝑠
Δ − 𝑜𝑢𝑡𝑝𝑢𝑡 𝑎𝑙𝑝ℎ𝑎𝑏𝑒𝑡 𝑜𝑟 𝑠𝑒𝑡 𝑜𝑓 𝑜𝑢𝑡𝑝𝑢𝑡 𝑠𝑦𝑚𝑏𝑜𝑙𝑠
𝛿 − 𝑖𝑛𝑝𝑢𝑡 𝑡𝑟𝑎𝑛𝑠𝑖𝑡𝑖𝑜𝑛 𝑓𝑢𝑛𝑐𝑡𝑖𝑜𝑛 𝑑𝑒𝑓𝑖𝑛𝑒𝑑 𝑏𝑦 𝛿: 𝑄𝑋Σ → Q
𝜆 − 𝑜𝑢𝑡𝑝𝑢𝑡 𝑡𝑟𝑎𝑛𝑠𝑖𝑡𝑖𝑜𝑛 𝑓𝑢𝑛𝑐𝑡𝑖𝑜𝑛 𝑑𝑒𝑓𝑖𝑛𝑒𝑑 𝑏𝑦 𝛿:𝑄 → Δ
𝑞0 − 𝑠𝑡𝑎𝑟𝑡 𝑠𝑡𝑎𝑡𝑒 , 𝑞0 ∈ 𝑄
MEALY MACHINE:
Definition: It was proposed by George H. Mealy. Mealy machine is a finite automata with output
where output depends on present state and present input. In this machine, transition is labeled with
input and output.
Mathematical representation of Mealy machine:
Mealy machine is formally defined as 6-tuple 𝑴 = (𝑸, 𝚺, 𝚫, 𝜹, 𝝀, 𝒒𝟎) Where
𝑀 -- 𝑀EALY 𝑀𝑎𝑐ℎ𝑖𝑛𝑒
𝑄 − 𝑓𝑖𝑛𝑖𝑡𝑒 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑠𝑡𝑎𝑡𝑒𝑠
Σ − 𝑖𝑛𝑝𝑢𝑡 𝑎𝑙𝑝ℎ𝑎𝑏𝑒𝑡 𝑜𝑟 𝑠𝑒𝑡 𝑜𝑓 𝑖𝑛𝑝𝑢𝑡 𝑠𝑦𝑚𝑏𝑜𝑙𝑠
Δ − 𝑜𝑢𝑡𝑝𝑢𝑡 𝑎𝑙𝑝ℎ𝑎𝑏𝑒𝑡 𝑜𝑟 𝑠𝑒𝑡 𝑜𝑓 𝑜𝑢𝑡𝑝𝑢𝑡 𝑠𝑦𝑚𝑏𝑜𝑙𝑠
𝛿 − 𝑖𝑛𝑝𝑢𝑡 𝑡𝑟𝑎𝑛𝑠𝑖𝑡𝑖𝑜𝑛 𝑓𝑢𝑛𝑐𝑡𝑖𝑜𝑛 𝑑𝑒𝑓𝑖𝑛𝑒𝑑 𝑏𝑦 𝛿: 𝑄𝑋Σ → Q
𝜆 − 𝑜𝑢𝑡𝑝𝑢𝑡 𝑡𝑟𝑎𝑛𝑠𝑖𝑡𝑖𝑜𝑛 𝑓𝑢𝑛𝑐𝑡𝑖𝑜𝑛 𝑑𝑒𝑓𝑖𝑛𝑒𝑑 𝑏𝑦 𝛿:𝑄𝑋Σ → Δ
𝑞0 − 𝑠𝑡𝑎𝑟𝑡 𝑠𝑡𝑎𝑡𝑒 𝑞0 ∈ 𝑄
Conversion of Moore Machine to Mealy machine:
1. Draw transition table of moore machine.
2. Draw transition table format for mealy machine.
3. Put present states of moore machine in present state of mealy machine.
4. Put next states for corresponding present states and input of moore machine in next states
for those present states and input of mealy machine.
5. For output, consider present state and output of moore machine.
6. Output for next state at input in mealy machine will be Output for that state as present
state in moore machine.

Conversion of Mealy Machine to Moore machine:

1. Draw transition table of mealy machine.
2. Observe next state and output columns .
3. If output differs for same next state, then break that state into number of states.
4. Change next states according to new set of states.
5. Put output in modified mealy machine.
6. Draw transition table format for moore machine.
7. Put present states and next states of modified mealy machine in present state and next
states of moore machine.
8. For output, consider next state and output of mealy machine.
9. Output for next state in moore machine will be Output for that state as present state in
mealy machine.

Differences between DFA and NFA:

DFA NFA
“it is a finite automata in which all the moves “it is a finite automata in which some of the
of a machine can be uniquely determined by moves of a machine cannot be uniquely
using current state and input symbol determined by using current state and input
symbol.
DFA is formally defined as 5-tuple NFA is formally defined as 5-tuple
𝑴 = (𝑸, 𝚺, 𝜹, 𝒒𝟎,𝑭) 𝑴 = (𝑸, 𝚺, 𝜹, 𝒒𝟎,𝑭)
where 𝑀 = 𝐹𝑖𝑛𝑖𝑡𝑒 𝑆𝑡𝑎𝑡𝑒 𝑀𝑎𝑐ℎ𝑖𝑛 where 𝑀 = 𝐹𝑖𝑛𝑖𝑡𝑒 𝑆𝑡𝑎𝑡𝑒 𝑀𝑎𝑐ℎ𝑖𝑛
𝑄 − 𝑓𝑖𝑛𝑖𝑡𝑒 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑠𝑡𝑎𝑡𝑒𝑠 𝑄 − 𝑓𝑖𝑛𝑖𝑡𝑒 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑠𝑡𝑎𝑡𝑒𝑠
Σ − 𝑖𝑛𝑝𝑢𝑡 𝑎𝑙𝑝ℎ𝑎𝑏𝑒𝑡 Σ − 𝑖𝑛𝑝𝑢𝑡 𝑎𝑙𝑝ℎ𝑎𝑏𝑒𝑡
𝛿 − 𝑡𝑟𝑎𝑛𝑠𝑖𝑡𝑖𝑜𝑛 𝑓𝑢𝑛𝑐𝑡𝑖𝑜𝑛 𝑑𝑒𝑓𝑖𝑛𝑒𝑑 𝑏𝑦 𝛿: 𝑄𝑋Σ → Q 𝛿 − 𝑡𝑟𝑎𝑛𝑠𝑖𝑡𝑖𝑜𝑛 𝑓𝑢𝑛𝑐𝑡𝑖𝑜𝑛 𝑑𝑒𝑓𝑖𝑛𝑒𝑑 𝑏𝑦 𝛿: 𝑄𝑋Σ ∪ {ε} → 2Q
𝑞0 − 𝑠𝑡𝑎𝑟𝑡 𝑠𝑡𝑎𝑡𝑒, 𝑞0 ∈ 𝑄 , 2Q ⊆ 𝑄
𝐹 − 𝑠𝑒𝑡 𝑜𝑓 𝑓𝑖𝑛𝑎𝑙 𝑠𝑡𝑎𝑡𝑒𝑠 𝐹 ⊆ 𝑄 𝑞0 − 𝑠𝑡𝑎𝑟𝑡 𝑠𝑡𝑎𝑡𝑒 𝑞0 ∈ 𝑄
𝐹 − 𝑠𝑒𝑡 𝑜𝑓 𝑓𝑖𝑛𝑎𝑙 𝑠𝑡𝑎𝑡𝑒𝑠 𝐹 ⊆ 𝑄
It does not allow any epsilon transitions It allows epsilon transitions
It takes less time to recognize input string. It takes more time to recognize input string.
It occupies more space. It occupies less space.
It accepts a string, if it is in one of the final It accepts a string, if some sequence of possible
states, after processing entire string. moves of a machine reaches final
state, after processing entire string.
It rejects a string, if it is in non-final states, It rejects a string, if no sequence of possible
after processing entire string. moves of a machine reaches final state, after
processing entire string.
It is bigger than NFA. It is smaller than DFA.
Differences between Moore Machine and mealy Machine:
Moore Machine Mealy Machine
It was proposed by Edward F. Moore. It was proposed by George H. Mealy.
Moore machine is a finite automata with Mealy machine is a finite automata with
output where output depends on present state output where output depends on present state
only. and present input.
In this machine, states are labeled with state In this machine, transition is labeled with
name and output. input and output.
Moore machine is formally defined as 6-tuple Mealy machine is formally defined as 6-tuple
𝑴 = (𝑸, 𝚺,𝚫, 𝜹, 𝝀, 𝒒𝟎) 𝑴 = (𝑸, 𝚺,𝚫, 𝜹, 𝝀, 𝒒𝟎)
where 𝑀 = 𝑀𝑜𝑜𝑟𝑒 𝑀𝑎𝑐ℎ𝑖𝑛𝑒 where 𝑀 = 𝑀ealy 𝑀𝑎𝑐ℎ𝑖𝑛𝑒
𝑄 − 𝑓𝑖𝑛𝑖𝑡𝑒 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑠𝑡𝑎𝑡𝑒𝑠 𝑄 − 𝑓𝑖𝑛𝑖𝑡𝑒 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑠𝑡𝑎𝑡𝑒𝑠
Σ − 𝑖𝑛𝑝𝑢𝑡 𝑎𝑙𝑝ℎ𝑎𝑏𝑒𝑡 Σ − 𝑖𝑛𝑝𝑢𝑡 𝑎𝑙𝑝ℎ𝑎𝑏𝑒𝑡
Δ − 𝑜𝑢𝑡𝑝𝑢𝑡 𝑎𝑙𝑝ℎ𝑎𝑏𝑒𝑡 Δ − 𝑜𝑢𝑡𝑝𝑢𝑡 𝑎𝑙𝑝ℎ𝑎𝑏𝑒𝑡
𝛿 − 𝑖𝑛𝑝𝑢𝑡 𝑡𝑟𝑎𝑛𝑠𝑖𝑡𝑖𝑜𝑛 𝑓𝑢𝑛𝑐𝑡𝑖𝑜𝑛 𝑑𝑒𝑓𝑖𝑛𝑒𝑑 𝑏𝑦 𝛿:𝑄𝑋Σ → Q 𝛿 − 𝑖𝑛𝑝𝑢𝑡 𝑡𝑟𝑎𝑛𝑠𝑖𝑡𝑖𝑜𝑛 𝑓𝑢𝑛𝑐𝑡𝑖𝑜𝑛 𝑑𝑒𝑓𝑖𝑛𝑒𝑑 𝑏𝑦 𝛿:𝑄𝑋Σ → Q
𝜆 − 𝑜𝑢𝑡𝑝𝑢𝑡 𝑡𝑟𝑎𝑛𝑠𝑖𝑡𝑖𝑜𝑛 𝑓𝑢𝑛𝑐𝑡𝑖𝑜𝑛 𝑑𝑒𝑓𝑖𝑛𝑒𝑑 𝑏𝑦 𝛿: 𝑄 → Δ 𝜆 − 𝑜𝑢𝑡𝑝𝑢𝑡 𝑡𝑟𝑎𝑛𝑠𝑖𝑡𝑖𝑜𝑛 𝑓𝑢𝑛𝑐𝑡𝑖𝑜𝑛 𝑑𝑒𝑓𝑖𝑛𝑒𝑑 𝑏𝑦 𝛿:𝑄𝑋Σ → Δ
𝑞0 − 𝑠𝑡𝑎𝑟𝑡 𝑠𝑡𝑎𝑡𝑒 𝑞0 ∈ Q 𝑞0 − 𝑠𝑡𝑎𝑟𝑡 𝑠𝑡𝑎𝑡𝑒 𝑞0 ∈ 𝑄

For input ɛ, output is λ(M0) For input ɛ, output is ɛ.

For input string of length ‘n’, output string For input string of length ‘n’, output string
consists of length ‘n+1’. consists of length ‘n’.

Example Problems of DFA

Ex 1: Design a FA with ∑ = {0, 1} accepts those string which starts with 1 and ends with 0.
Solution: The FA will have a start state q0 from which only the edge with input 1 will go to the next
state.

In state q1, if we read 1, we will be in state q1, but if we read 0 at state q1, we will reach to state q2
which is the final state. In state q2, if we read either 0 or 1, we will go to q2 state or q1 state
respectively. Note that if the input ends with 0, it will be in the final state.

Ex 2: Design a FA with ∑ = {0, 1} accepts the only input 101.

Solution:

In the given solution, we can see that only input 101 will be accepted. Hence, for input 101, there is
no other path shown for other input.
Ex 3: Design FA with ∑ = {0, 1} accepts even number of 0's and even number of 1's.
Solution: This FA will consider four different stages for input 0 and input 1. The stages could be:

Here q0 is a start state and the final state also. Note carefully that a symmetry of 0's and 1's is
maintained. We can associate meanings to each state as:
q0: state of even number of 0's and even number of 1's.
q1: state of odd number of 0's and even number of 1's.
q2: state of odd number of 0's and odd number of 1's.
q3: state of even number of 0's and odd number of 1's.

Ex 4: Design FA with ∑ = {0, 1} accepts the set of all strings with three consecutive 0's.
Solution: The strings that will be generated for this particular languages are 000, 0001, 1000, 10001,
.... in which 0 always appears in a clump of 3. The transition graph is as follows:

Note that the sequence of triple zeros is maintained to reach the final state.

Ex 5: Design a DFA L(M) = {w | w ε {0, 1}*} and W is a string that does not contain
consecutive 1's.
Solution: When three consecutive 1's occur the DFA will be:

Here two consecutive 1's or single 1 is acceptable, hence

The stages q0, q1, q2 are the final states. The DFA will generate the strings that do not contain
consecutive 1's like 10, 110, 101,..... etc.

Ex 6: Design a FA with ∑ = {0, 1} accepts the strings with an even number of 0's followed by
single 1.
Solution: The DFA can be shown by a transition diagram as:
Example Problems of NDFA
1. NFA stands for non-deterministic finite automata. It is easy to construct an NFA than DFA
for a given regular language.
2. The finite automata are called NFA when there exist many paths for specific input from the
current state to the next state.
3. Every NFA is not DFA, but each NFA can be translated into DFA.
4. NFA is defined in the same way as DFA but with the following two exceptions, it contains
multiple next states, and it contains ε transition.

In the following image, we can see that from state q0 for input a, there are two next states q1 and q2,
similarly, from q0 for input b, the next states are q0 and q1. Thus it is not fixed or determined that
with a particular input where to go next. Hence this FA is called non-deterministic finite automata.

Formal definition of NFA: NFA also has five states same as DFA, but with different transition function, as
shown follows:
δ: Q x ∑ →2Q
where, Q: finite set of states
∑: finite set of the input symbol
q0: initial state
F: final state
δ: Transition function
Graphical Representation of an NFA :-An NFA can be represented by digraphs called state
diagram. In which:
1. The state is represented by vertices.
2. The arc labeled with an input character show the transitions.
3. The initial state is marked with an arrow.
4. The final state is denoted by the double circle.

Example 1: Q = {q0, q1, q2}

∑ = {0, 1}
q0 = {q0}
F = {q2}

Solution: Transition diagram:

Transition Table:
Present State Next state for Input 0 Next State of Input 1

→q0 q0, q1 q1

q1 q2 q0

*q2 q2 q1, q2

In the above diagram, we can see that when the current state is q0, on input 0, the next state will be
q0 or q1, and on 1 input the next state will be q1. When the current state is q1, on input 0 the next
state will be q2 and on 1 input, the next state will be q0. When the current state is q2, on 0 input the
next state is q2, and on 1 input the next state will be q1 or q2.

Example 2: NFA with ∑ = {0, 1} accepts all strings with 01.

Solution:

Transition Table:
Present State Next state for Input 0 Next State of Input 1

→q0 q1 ε

q1 ε q2

*q2 q2 q2

Example 3: NFA with ∑ = {0, 1} and accept all string of length at least 2.

Solution:

Transition Table:
Present State Next state for Input 0 Next State of Input 1

→q0 q1 q1
q1 q2 q2

*q2 ε ε
Example 4: Design a NFA for the transition table as given below:
Present State 0 1

→q0 q0, q1 q0, q2

q1 q3 ε
q2 q2, q3 q3
→q3 q3 q3
Solution: The transition diagram can be drawn by using the mapping function as given in the table.

Here,
δ(q0, 0) = {q0, q1}
δ(q0, 1) = {q0, q2}
Then, δ(q1, 0) = {q3}
Then, δ(q2, 0) = {q2, q3}
δ(q2, 1) = {q3}
Then, δ(q3, 0) = {q3}
δ(q3, 1) = {q3}

Example 5: Design an NFA with ∑ = {0, 1} accepts all string ending with 01.
Solution:

Hence, NFA would be:

Example 6:Design an NFA with ∑ = {0, 1} in which double '1' is followed by double '0'.
Solution: The FA with double 1 is as follows:

It should be immediately followed by double 0. Then,

Now before double 1, there can be any string of 0 and 1. Similarly, after double 0, there can be any
string of 0 and 1. Hence the NFA becomes:

Now considering the string 01100011

q0 → q1 → q2 → q3 → q4 → q4 → q4 → q4

Example 7: Design an NFA in which all the string contain a substring 1110.

Solution: The language consists of all the string containing substring 1010. The partial transition
diagram can be:

Now as 1010 could be the substring. Hence we will add the inputs 0's and 1's so that the substring
1010 of the language can be maintained. Hence the NFA becomes:

Transition table for the above transition diagram can be given below:
Present State 0 1

→q1 q1 q1, q2
q2 q3
q3 q4
q4 q5
*q5 q5 q5
Consider a string 111010,
δ(q1, 111010) = δ(q1, 1100)
= δ(q1, 100)
= δ(q2, 00)
Got stuck! As there is no path from q2 for input symbol 0. We can process string 111010 in another
way.
δ(q1, 111010) = δ(q2, 1100)
= δ(q3, 100)
= δ(q4, 00)
= δ(q5, 0)
= δ(q5, ε)
As state q5 is the accept state. We get the complete scanned, and we reached to the final state.
Example 8: Design an NFA with ∑ = {0, 1} accepts all string in which the third symbol from the
right end is always 0.
Solution:

Thus we get the third symbol from the right end as '0' always. The NFA can be:

The above image is an NFA because in state q0 with input 0, we can either go to state q0 or q1.

Eliminating ε Transitions
NFA with ε can be converted to NFA without ε, and this NFA without ε can be converted to DFA.
To do this, we will use a method, which can remove all the ε transition from given NFA. The
method will be:
1. Find out all the ε transitions from each state from Q. That will be called as ε-closure{q1}
where qi ∈ Q.
2. Then δ' transitions can be obtained. The δ' transitions mean a ε-closure on δ moves.
3. Repeat Step-2 for each input symbol and each state of given NFA.
4. Using the resultant states, the transition table for equivalent NFA without ε can be built.

Example: Convert the following NFA with ε to NFA without ε.

Solutions: We will first obtain ε-closures of q0, q1 and q2 as follows:

ε-closure(q0) = {q0}
ε-closure(q1) = {q1, q2}
ε-closure(q2) = {q2}
Now the δ' transition on each input symbol is obtained as:
δ'(q0, a) = ε-closure(δ(δ^(q0, ε),a))
= ε-closure(δ(ε-closure(q0),a))
= ε-closure(δ(q0, a))
= ε-closure(q1)
= {q1, q2}

δ'(q0, b) = ε-closure(δ(δ^(q0, ε),b))

= ε-closure(δ(ε-closure(q0),b))
= ε-closure(δ(q0, b))
=Ф

Now the δ' transition on q1 is obtained as:

δ'(q1, a) = ε-closure(δ(δ^(q1, ε),a))
= ε-closure(δ(ε-closure(q1),a))
= ε-closure(δ(q1, q2), a)
= ε-closure(δ(q1, a) ∪ δ(q2, a))
= ε-closure(Ф ∪ Ф)
=Ф

δ'(q1, b) = ε-closure(δ(δ^(q1, ε),b))

= ε-closure(δ(ε-closure(q1),b))
= ε-closure(δ(q1, q2), b)
= ε-closure(δ(q1, b) ∪ δ(q2, b))
= ε-closure(Ф ∪ q2)
= {q2}
The δ' transition on q2 is obtained as:
δ'(q2, a) = ε-closure(δ(δ^(q2, ε),a))
= ε-closure(δ(ε-closure(q2),a))
= ε-closure(δ(q2, a))
= ε-closure(Ф)
=Ф

δ'(q2, b) = ε-closure(δ(δ^(q2, ε),b))

= ε-closure(δ(ε-closure(q2),b))
= ε-closure(δ(q2, b))
= ε-closure(q2)
= {q2}
Now we will summarize all the computed δ' transitions:
δ'(q0, a) = {q0, q1}
δ'(q0, b) = Ф
δ'(q1, a) = Ф
δ'(q1, b) = {q2}
δ'(q2, a) = Ф
δ'(q2, b) = {q2}
The transition table can be:
States a b

→q0 {q1, q2} Ф

*q1 Ф {q2}
*q2 Ф {q2}
State q1 and q2 become the final state as ε-closure of q1 and q2 contain the final state q2. The
NFA can be shown by the following transition diagram:
Conversion from NFA to DFA
In NFA, when a specific input is given to the current state, the machine goes to multiple states. It can
have zero, one or more than one move on a given input symbol. On the other hand, in DFA, when a
specific input is given to the current state, the machine goes to only one state. DFA has only one
move on a given input symbol.

Let, M = (Q, ∑, δ, q0, F) is an NFA which accepts the language L(M). There should be equivalent
DFA denoted by M' = (Q', ∑', q0', δ', F') such that L(M) = L(M').

Steps for converting NFA to DFA:

Step 1: Initially Q' = ϕ
Step 2: Add q0 of NFA to Q'. Then find the transitions from this start state.
Step 3: In Q', find the possible set of states for each input symbol. If this set of states is not in Q',
then add it to Q'.
Step 4: In DFA, the final state will be all the states which contain F(final states of NFA)

Example 1: Convert the given NFA to DFA.

Solution: For the given transition diagram we will first construct the transition table.
State 0 1

→q0 q0 q1

q1 {q1, q2} q1

*q2 q2 {q1, q2}

Now we will obtain δ' transition for state q0.
δ'([q0], 0) = [q0]
δ'([q0], 1) = [q1]
The δ' transition for state q1 is obtained as:
δ'([q1], 0) = [q1, q2] (new state generated)
δ'([q1], 1) = [q1]
The δ' transition for state q2 is obtained as:
δ'([q2], 0) = [q2]
δ'([q2], 1) = [q1, q2]
Now we will obtain δ' transition on [q1, q2].
δ'([q1, q2], 0) = δ(q1, 0) ∪ δ(q2, 0)
= {q1, q2} ∪ {q2}
= [q1, q2]
δ'([q1, q2], 1) = δ(q1, 1) ∪ δ(q2, 1)
= {q1} ∪ {q1, q2}
= {q1, q2}
= [q1, q2]
The state [q1, q2] is the final state as well because it contains a final state q2. The transition table for
the constructed DFA will be:
State 0 1

→[q0] [q0] [q1]

[q1] [q1, q2] [q1]

*[q2] [q2] [q1, q2]

*[q1, q2] [q1, q2] [q1, q2]

The Transition diagram will be:

The state q2 can be eliminated because q2 is an unreachable state.

Example 2: Convert the given NFA to DFA.

Solution: For the given transition diagram we will first construct the transition table.

State 0 1

→q0 {q0, q1} {q1}

*q1 ϕ {q0, q1}

Now we will obtain δ' transition for state q0.
δ'([q0], 0) = {q0, q1}
= [q0, q1] (new state generated)
δ'([q0], 1) = {q1} = [q1]
The δ' transition for state q1 is obtained as:
δ'([q1], 0) = ϕ
δ'([q1], 1) = [q0, q1]
Now we will obtain δ' transition on [q0, q1].
δ'([q0, q1], 0) = δ(q0, 0) ∪ δ(q1, 0)
= {q0, q1} ∪ ϕ
= {q0, q1}
= [q0, q1]

Similarly,
δ'([q0, q1], 1) = δ(q0, 1) ∪ δ(q1, 1)
= {q1} ∪ {q0, q1}
= {q0, q1}
= [q0, q1]
As in the given NFA, q1 is a final state, then in DFA wherever, q1 exists that state becomes a final
state. Hence in the DFA, final states are [q1] and [q0, q1]. Therefore set of final states
F = {[q1], [q0, q1]}. The transition table for the constructed DFA will be:
State 0 1

→[q0] [q0, q1] [q1]

*[q1] ϕ [q0, q1]

*[q0, q1] [q0, q1] [q0, q1]

The Transition diagram will be:

Even we can change the name of the states of DFA.

Suppose
A = [q0]
B = [q1]
C = [q0, q1]
With these new names the DFA will be as follows:
Moore Machine
Moore machine is a finite state machine in which the next state is decided by the current state and
current input symbol. The output symbol at a given time depends only on the present state of the
machine. Moore machine can be described by 6 tuples (Q, q0, ∑, O, δ, λ) where,

Q: finite set of states

q0: initial state of machine
∑: finite set of input symbols
O: output alphabet
δ: transition function where Q × ∑ → Q
λ: output function where Q → O

Example 1:The state diagram for Moore Machine is

Transition table for Moore Machine is:

In the above Moore machine, the output is represented with each input state separated by /.
The output length for a Moore machine is greater than input by 1.
Input: 010
Transition: δ (q0,0) => δ(q1,1) => δ(q1,0) => q2
Output: 1110(1 for q0, 1 for q1, again 1 for q1, 0 for q2)

Example 2: Design a Moore machine to generate 1's complement of a given binary number.
Solution: To generate 1's complement of a given binary number the simple logic is that if the input is
0 then the output will be 1 and if the input is 1 then the output will be 0. That means there are three
states. One state is start state. The second state is for taking 0's as input and produces output as 1. The
third state is for taking 1's as input and producing output as 0.
Hence the Moore machine will be,
For instance, take one binary number 1011 then

Input 1 0 1 1

State q0 q2 q1 q2 q2

Output 0 0 1 0 0

Thus we get 00100 as 1's complement of 1011, we can neglect the initial 0 and the output which we
get is 0100 which is 1's complement of 1011.
The transaction table is as follows:

Thus Moore machine M = (Q, q0, ∑, O, δ, λ); where Q = {q0, q1, q2}, ∑ = {0, 1}, O = {0, 1}. the
transition table shows the δ and λ functions.

Example 3: Design a Moore machine for a binary input sequence such that if it has a substring
101, the machine output A, if the input has substring 110, it outputs B otherwise it outputs C.
Solution: For designing such a machine, we will check two conditions, and those are 101 and 110. If
we get 101, the output will be A, and if we recognize 110, the output will be B. For other strings, the
output will be C.

The partial diagram will be:

Now we will insert the possibilities of 0's and 1's for each state. Thus the Moore machine becomes:
Example 4: Construct a Moore machine that determines whether an input string contains an
even or odd number of 1's. The machine should give 1 as output if an even number of 1's are in
the string and 0 otherwise.
Solution: The Moore machine will be:

This is the required Moore machine. In this machine, state q1 accepts an odd number of 1's and state
q0 accepts even number of 1's. There is no restriction on a number of zeros. Hence for 0 input, self-
loop can be applied on both the states.

Example 5: Design a Moore machine with the input alphabet {0, 1} and output alphabet {Y,
N} which produces Y as output if input sequence contains 1010 as a substring otherwise, it
produces N as output.
Solution: The Moore machine will be:

Mealy Machine
A Mealy machine is a machine in which output symbol depends upon the present input symbol and
present state of the machine. In the Mealy machine, the output is represented with each input symbol
for each state separated by /. The Mealy machine can be described by 6 tuples (Q, q0, ∑, O, δ, λ')
where
Q: finite set of states
q0: initial state of machine
∑: finite set of input alphabet
O: output alphabet
δ: transition function where Q × ∑ → Q
λ': output function where Q × ∑ →O

Example 1: Design a Mealy machine for a binary input sequence such that if it has a substring
101, the machine output A, if the input has substring 110, it outputs B otherwise it outputs C.

Solution: For designing such a machine, we will check two conditions, and those are 101 and 110. If
we get 101, the output will be A. If we recognize 110, the output will be B. For other strings the
output will be C.

The partial diagram will be:

Now we will insert the possibilities of 0's and 1's for each state. Thus the Mealy machine becomes:

Example 2: Design a mealy machine that scans sequence of input of 0 and 1 and generates
output 'A' if the input string terminates in 00, output 'B' if the string terminates in 11, and
output 'C' otherwise.

Solution: The mealy machine will be:

Conversion from Mealy machine to Moore Machine

In Moore machine, the output is associated with every state, and in Mealy machine, the output is
given along the edge with input symbol. To convert Moore machine to Mealy machine, state output
symbols are distributed to input symbol paths. But while converting the Mealy machine to Moore
machine, we will create a separate state for every new output symbol and according to incoming and
outgoing edges are distributed.

The following steps are used for converting Mealy machine to the Moore machine:
Step 1: For each state(Qi), calculate the number of different outputs that are available in the
transition table of the Mealy machine.
Step 2: Copy state Qi, if all the outputs of Qi are the same. Break qi into n states as Qin, if it has n
distinct outputs where n = 0, 1, 2....
Step 3: If the output of initial state is 0, insert a new initial state at the starting which gives 1 output.
Example 1: Convert the following Mealy machine into equivalent Moore machine.

Solution: Transition table for above Mealy machine is as follows:

1. For state q1, there is only one incident edge with output 0. So, we don't need to split this state
in Moore machine.
2. For state q2, there is 2 incident edge with output 0 and 1. So, we will split this state into two
states q20( state with output 0) and q21(with output 1).
3. For state q3, there is 2 incident edge with output 0 and 1. So, we will split this state into two
states q30( state with output 0) and q31( state with output 1).
4. For state q4, there is only one incident edge with output 0. So, we don't need to split this state
in Moore machine.
5. Transition table for Moore machine will be:

Transition diagram for Moore machine will be:

Example 2: Convert the following Mealy machine into equivalent Moore machine.

Solution: Transition table for above Mealy machine is as follows:

The state q1 has only one output. The state q2 and q3 have both output 0 and 1. So we will create two
states for these states. For q2, two states will be q20(with output 0) and q21(with output 1).
Similarly, for q3 two states will be q30(with output 0) and q31(with output 1).

Transition table for Moore machine will be:

Transition diagram for Moore machine will be:

Conversion from Moore machine to Mealy Machine

In the Moore machine, the output is associated with every state, and in the mealy machine, the output
is given along the edge with input symbol. The equivalence of the Moore machine and Mealy
machine means both the machines generate the same output string for same input string.

We cannot directly convert Moore machine to its equivalent Mealy machine because the length of
the Moore machine is one longer than the Mealy machine for the given input. To convert Moore
machine to Mealy machine, state output symbols are distributed into input symbol paths. We are
going to use the following method to convert the Moore machine to Mealy machine.

Method for conversion of Moore machine to Mealy machine

Let M = (Q, ∑, δ, λ, q0) be a Moore machine. The equivalent Mealy machine can be represented by
M' = (Q, ∑, δ, λ', q0). The output function λ' can be obtained as: λ' (q, a) = λ(δ(q, a))

Example 1: Convert the following Moore machine into its equivalent Mealy machine.

Solution: The transition table of given Moore machine is as follows:

Q a b Output(λ)

q0 q0 q1 0

q1 q0 q1 1

The equivalent Mealy machine can be obtained as follows:

λ' (q0, a) = λ(δ(q0, a))
= λ(q0)
=0
λ' (q0, b) = λ(δ(q0, b))
= λ(q1)
=1
The λ for state q1 is as follows:
λ' (q1, a) = λ(δ(q1, a))
= λ(q0)
=0
λ' (q1, b) = λ(δ(q1, b))
= λ(q1)
=1
Hence the transition table for the Mealy machine can be drawn as follows:

The equivalent Mealy machine will be,

Note: The length of output sequence is 'n+1' in Moore machine and is 'n' in the Mealy
machine.
Example 2:Convert the given Moore machine into its equivalent Mealy machine.

Solution: The transition table of given Moore machine is as follows:

Q a b Output(λ)

q0 q1 q0 0

q1 q1 q2 0

q2 q1 q0 1

The equivalent Mealy machine can be obtained as follows:

λ' (q0, a) = λ(δ(q0, a))
= λ(q1)
=0
λ' (q0, b) = λ(δ(q0, b))
= λ(q0)
=0
The λ for state q1 is as follows:
λ' (q1, a) = λ(δ(q1, a))
= λ(q1)
=0
λ' (q1, b) = λ(δ(q1, b))
= λ(q2)
=1
The λ for state q2 is as follows:
λ' (q2, a) = λ(δ(q2, a))
= λ(q1)
=0
λ' (q2, b) = λ(δ(q2, b))
= λ(q0)
=0
Hence the transition table for the Mealy machine can be drawn as follows:

The equivalent Mealy machine will be,

Example 3:Convert the given Moore machine into its equivalent Mealy machine.
Q a b Output(λ)

q0 q0 q1 0

q1 q2 q0 1

q2 q1 q2 2

Solution: The transaction diagram for the given problem can be drawn as:
The equivalent Mealy machine can be obtained as follows:
λ' (q0, a) = λ(δ(q0, a))
= λ(q0)
=0
λ' (q0, b) = λ(δ(q0, b))
= λ(q1)
=1
The λ for state q1 is as follows:
λ' (q1, a) = λ(δ(q1, a))
= λ(q2)
=2
λ' (q1, b) = λ(δ(q1, b))
= λ(q0)
=0
The λ for state q2 is as follows:
λ' (q2, a) = λ(δ(q2, a))
= λ(q1)
=1
λ' (q2, b) = λ(δ(q2, b))
= λ(q2)
=2
Hence the transition table for the Mealy machine can be drawn as follows:

The equivalent Mealy machine will be,