1|Page © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

Unit – I
Formal Language Theory and Finite
Automata
1. Finite Automata (FA)

1.1 Introduction to Formal Language Theory

Formal Language Theory is the foundation of automata theory and compiler design. It deals
with the structure and behavior of languages, which are defined using formal rules.

To understand this, we start with some basic terms:

1. Symbol: A basic atomic unit or character. It cannot be broken further.

 Examples: a, b, 0, 1, #, $

2. Alphabet (Σ): A finite, non-empty set of symbols. Denoted by Σ (sigma).

 Example: Σ = {0, 1} (binary alphabet)

Σ = {a, b, c}

3. String / Word: A finite sequence of symbols taken from an alphabet. It is denoted by

lowercase letters like w.

 Length of string = number of symbols in it.

 Examples: w = 0101

w = bbab

4. Empty String (ε): A string with no symbols. Denoted by ε (epsilon). Length = 0.

5. Length of a String: Denoted by ∣w∣, where w is the string.

 Example: ∣aabba∣ = 5, ∣ε∣ = 0

6. Power of an Alphabet (Σn): Set of all strings of length n.

 Σ*: Set of all possible strings (including ε) over Σ.

2|Page © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

 Σ+: All strings excluding ε.

 Example (for Σ = {a, b}): Σ2 = {aa, ab, ba, bb}

Σ* = {ε, a, b, aa, ab, ba, bb, ...}

7. Language (L): A set of strings formed using the alphabet. A language can be finite or
infinite.

 Example: L = {w ∈ {0, 1} ∗ ∣ w has even number of 1’s}

1.2 An informal picture of FA

A Finite Automaton (FA) is a simple abstract machine used to recognize patterns within input
strings. It has a limited (finite) memory and operates by reading input symbols one at a
time, moving from one state to another.

FA is like a simple robot that:

 Starts in an initial state.

 Reads input symbol by symbol.

 Changes state based on the current symbol and current state.

 May accept or reject the input string after reading it fully.

It cannot remember anything beyond its current state (no external memory like a stack or
tape).

Components of the 5-Tuple of FA

A Finite Automaton (FA) is formally defined by a 5-tuple:

M = (Q, Σ, δ, q0, F)

1. Q – Set of States: This is the finite set of all possible states the automaton can be in. Each
state represents a condition or status of the machine at a particular moment.

 Notation: Q = {q0, q1, q2, ..., qn}

2. Σ – Input Alphabet: A finite set of symbols that the machine can read as input. These
symbols form the language that the automaton operates on.

 Notation: Σ = {a, b, 0, 1, ...}

3|Page © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

3. δ – Transition Function: This function tells the automaton how to move from one state to
another based on the input symbol. In a DFA, δ gives exactly one next state for a given
(current state, input symbol) pair.

 Notation: δ: Q × Σ → Q

 Example: δ (q0, 1). This means if the current state is q0 and input is 1, move to state q1.

4. q₀ – Initial (Start) State: The state where the automaton begins execution before any input
is read. It must be one of the states in Q.

 Notation: q0 ∈ Q

5. F – Set of Final (Accepting) States: Subset of Q containing states that accept the input
string. If the automaton finishes reading the input and is in one of these states, the string is
accepted.

 Notation: F ⊆ Q

Transi on Diagram

A transition diagram is a visual way to represent a DFA using states and transitions. It shows
how the machine moves from one state to another based on input symbols.

Components of a Transition Diagram:

1. States: Represented by circles (e.g., q0, q1, etc.)

o Final states are shown as double circles (like q3 in this diagram).

o Initial state has an incoming arrow with no origin (→ q0 here).

2. Input Alphabet (Σ): Set of allowed input symbols.

o In this diagram, the input symbols are: a and b.

3. Transitions (δ): Represented by arrows labeled with input symbols.

o These show how the automaton moves based on the current symbol.
4|Page © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

In the above diagram:

States:

 Q = {q0, q1, q2, q3}

 q0 is the initial state (indicated by the arrow entering it).

 q3 is the final state (indicated by the double circle).

Transitions:

From q0:

 On a → go to q1

 On b → go to q2

From q1:

 On a → stay in q1 (self-loop)

 On b → go to q3

From q2:
5|Page © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

 On a → go to q3

 On b → stay in q2 (self-loop)

From q3:

 On a or b → stay in q3 (self-loop on both)

Let’s test the string ab:

 Start at q0

 Read a → go to q1

 Read b → go to q3 (final state) → So, ab is accepted.

Transi on Table

A Transition Table is a tabular representation of a transition function δ of a DFA.

It shows how the automaton moves from one state to another for each symbol in the input
alphabet.

Current State Input = a Input = b

q0 q1 q2

q1 q1 q3

q2 q3 q2

q3 q3 q3

 Each row = current state.

 Each column = input symbol (a or b).

 Each cell = next state to go to, based on input.

Example:

 δ (q0, a) = q1

 δ (q1, b) = q3

 δ (q3, b) = q3 (self-loop)
6|Page © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

Example: Elevator System with Three Floors: FA Interpretation

 Goal: To model how an elevator moves between three floors using a Finite Automaton
(FA) with states representing each floor.

 States (Q):

o q0: Ground floor

o q1: First floor

o q2: Second floor

 Input Alphabet (Σ):

o 0: Go to the ground floor

o 1: Go to the first floor

o 2: Go to the second floor

 Transition System − The transition system of the lift can be represented as a directed
graph.

In this directed graph, circles denote states (Q0, Q1, Q2). Directed edges represent transitions
based on input symbols.

The transition system of the lift can be visualized as the above-mentioned directed graph with
three states: Q0 (ground floor), Q1 (first floor), and Q2 (second floor).

Each state is represented by a circle. The initial state, Q0, is indicated by an inward arrow.
Transitions between states are depicted by directed edges based on input symbols.

 From 0, an input of 0 leads to Q0 (self-loop), an input of 1 leads to Q1, and an input of

2 leads to Q2.
7|Page © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

 From 1, an input of 0 transitions to Q0, an input of 1 remains in Q1 (self-loop), and an

input of 2 transitions to Q2.

 From 2, an input of 0 transitions to Q0, an input of 1 transitions to Q1, and an input of 2

remains in Q2 (self-loop).

 The final state, 2, is represented by a double circle.

1.3 Finite State Machine (FSM)

A Finite State Machine (FSM) is a mathematical model of computation that behaves like a
machine with a finite number of states and changes between them based on input symbols.

It is used to model systems that have a fixed number of conditions or modes (states) and
respond to external inputs.

A Finite State Machine is defined as:

M = (Q, Σ, δ, q0, F)

Where:

 Q = Finite set of states

 Σ = Finite input alphabet (set of symbols)

 δ = Transition function: δ: Q × Σ → Q

 q₀ = Initial state (q0 ∈ Q)

 F = Set of final (accepting) states (F ⊆ Q)

How FSM Works:

1. The FSM starts at the initial state.

2. It reads the input string one symbol at a time.

3. It follows transitions (defined by δ) based on the current symbol and current state.

4. When the entire input is processed:

o If it ends in a final state, the input is accepted.

o Otherwise, it is rejected.
8|Page © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

Types of FSM:

1. Deterministic Finite Automaton (DFA):

o For each state and input symbol, exactly one transition exists.

o No ambiguity.

2. Nondeterministic Finite Automaton (NFA):

o For a state and input symbol, multiple transitions may be possible.

o May include ε-transitions (without consuming input).

Every NFA can be converted into an equivalent DFA.

1.4 Language accepted by FA

A language accepted by a FA is the set of all strings that the automaton accepts (i.e., ends in
a final state after reading the entire input).

Formal Definition:

Let M = (Q, Σ, δ, q0, F) be a finite automaton.

Then, the language accepted by M is:

L(M) = {w ∈ Σ* ∣ δ* (q0, w) ∈ F}

Where:

 w = input string made of symbols from alphabet Σ

 Σ* = extended transition function (handles entire strings)

 q0 = initial state

 F = set of accepting (final) states

 δ* (q0, w) = final state reached after reading all of w

Key Points:

If a string causes the FA to end in a final state → the string is accepted.

The collection of all such strings forms the language accepted by the FA.

1.5 Definition of Regular Language

9|Page © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

A regular language is a type of formal language that can be recognized or accepted by a finite
automaton (FA).

Formal Definition:

A language L over an alphabet Σ is called regular if:

There exists a finite automaton (DFA or NFA) such that

L = L(M), where M is the automaton.

Key Points:

 Every language that can be accepted by a DFA or NFA is regular.

 Regular languages can also be described using regular expressions.

 They are the simplest and most restricted class in the Chomsky hierarchy.

Basic Regular Languages:

 ∅ (empty language)

 {ε} (only empty string)

 {a}, {b}, etc. for any symbol in Σ

Example:

Let FA accept binary strings with even number of zeros.

Then: L = {00, 0000, 000000, ...}

All these strings, when processed by the FA, end in a final state, so they belong to the regular
language.

2. FA without output

2.1 Deterministic Finite Automata (DFA)

10 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

A Deterministic Finite Automaton (DFA) is a type of finite automaton where for each state
and input symbol, there is exactly one defined transition.

It is a machine that accepts or rejects strings deterministically — no ambiguity in transitions.

Formal Definition of DFA:

A DFA is defined by a 5-tuple:

M = (Q, Σ, δ, q0, F), where

Symbol Meaning

Q Finite set of states

Σ Finite input alphabet

δ Transition function: Q × Σ → Q

q0 Initial state, where the FA starts

F Set of final/accepting states

Characteristics of DFA:

1. Determinism: For every state and input, only one transition is defined.

2. No ε-transitions: DFA cannot change states without input.

3. Every symbol is processed one at a time.

Example 2.1.1 Design a DFA which checks whether a given binary number is divisible by 3.

Logic:

We track the remainder when the binary number is divided by 3.

 States: q0 → remainder 0 (divisible)

11 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

q1 → remainder 1

q2 → remainder 2

 Start state: q0

 Final state: q0 (since remainder 0 means divisible by 3)

 Input symbols: {0, 1}

Transition Table

State Input 0 Input 1

→ *q0 q0 q1

q1 q2 q0

q2 q1 q2

Explanation of transitions

 Appending a 0 in binary = multiply by 2.

 Appending a 1 in binary = multiply by 2, then add 1.

 Transitions are based on taking the remainder mod 3 after each step.

Example 2.1.2 Design an FA which checks whether a given binary number is even.

A binary number is even if its last bit is 0. So, we only need to look at the last input symbol.

FA Components

 States:
q0 → even number (last bit 0) Final State

q1 → odd number (last bit 1)

12 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

 Alphabet: {0, 1}

 Start State: q0 (assume empty string is 0, which is even)

 Final States: { q0 }

Transition Table

State Input 0 Input 1

→* q0 q0 q1

q1 q0 q1

Explanation

 If we are in even state (q0) and read 0, we stay in even state.

 If we are in even state and read 1, it becomes odd → move to q1.

 If we are in odd state (q1) and read 0, it becomes even → move to q0.

 If we are in odd state and read 1, it stays odd.

Example 2.1.3 Design a DFA which accepts even number of 0’s and even number of 1’s.

We need to track two properties at once:

1. Whether the count of 0’s so far is even or odd

2. Whether the count of 1’s so far is even or odd

This gives 4 states:

 q0 → Even 0’s, Even 1’s (Final state)

13 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

 q1 → Odd 0’s, Even 1’s

 q2 → Odd 0’s, Odd 1’s

 q3 → Even 0’s, Odd 1’s

Transition Table

State Input 0 Input 1

→* q0 q1 q3

q1 q0 q2

q2 q3 q1

q3 q2 q0

Explanation

 Reading 0 changes the parity of 0’s but leaves 1’s unchanged.

 Reading 1 changes the parity of 1’s but leaves 0’s unchanged.

 Only q0 (both even) is final.

Example 2.1.4 Design finite automata for accepting strings, over Σ = {0, 1}, with even number
of 0’s and odd number of 1’s.

Hint: Only the final state changes!

Example 2.1.5 Design a DFA which can accept a decimal number divisible by 3.

A number is divisible by 3 if the sum of its digits is divisible by 3.

We will use modulo 3 arithmetic to keep track of the remainder when the number formed so
far is divided by 3.
14 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

States:

 q0 → remainder 0 (divisible by 3) — accepting state

 q1 → remainder 1

 q2 → remainder 2

Transition Table:

Current State Input

0, 3, 6, 9 1, 4, 7 2, 5, 8
→ *q0 q0 q1 q2
q1 q1 q2 q0
q2 q2 q0 q1

Formal Definition of DFA:

 States: {q0, q1, q2}

 Alphabet: {0,1,2,3,4,5,6,7,8,9}

 Start State: q0

 Accepting State: q0

 Transition Function: As described above.

Example:

 Input: 120

o q0 120
15 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

o 1 q1 20

o 12 q0 0

o 120 q0

o Ends in q0 → Accepted

Example 2.1.6 Design DFA to accept L, where L = {Strings in which ‘a’ always appears
tripled} over the set Σ = {a, b}

To design a Deterministic Finite Automaton (DFA) that accepts the language:

L = {strings in which ’a’ always appears tripled over the alphabet Σ = {a,b}, we need to ensure
that every occurrence of 'a' in the string is part of a triple "aaa". That is:

 No single 'a' or double 'aa' is allowed.

 Every 'a' must be in a group of exactly three consecutive 'a's.

 'b' can appear freely anywhere in the string.

States:

 q0 – Start and accepting state (seen 0 a’s in a group)

 q1 – Seen 1 ‘a’ in a group

 q2 – Seen 2 consecutive ‘a’s

 q3 – Seen a complete group of 3 ‘a’s

Transition Table
16 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

Current State Input a Input b

→ q0 q1 q0

q1 q2 qd

q2 q3 qd

* q3 (accept) q1 q3

qd (dead) qd qd

Example 2.1.7 Draw DFA for the following language over {0, 1}

i) Number of 1's in multiples of 3.

ii) Number of 1's is not multiple of 3.

 The idea is to track the remainder when the number of 1’s seen so far is divided by 3.

 So, we define 3 states:

o q0: number of 1’s seen so far ≡ 0 mod 3

o q1: number of 1’s seen so far ≡ 1 mod 3

o q2: number of 1’s seen so far ≡ 2 mod 3

On reading 0, we stay in the same state because we’re only counting 1’s.

(i) DFA for "Number of 1's is a multiple of 3"

Alphabet: {0, 1}

Accepting state: q0 (because 0, 3, 6, ... are multiples of 3)

Transition Table:
17 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

State Input 0 Input 1

→ *q0 q0 q1

q1 q1 q2

q2 q2 q0

(ii) DFA for "Number of 1's is not a multiple of 3"

This is just the complement of the above DFA.

Accepting states: q1, q2

Same transition table:

State Input 0 Input 1

→ q0 q0 q1

*q1 q1 q2

*q2 q2 q0

Example 2.1.8 Draw FA for strings which do not contain ‘00’ as a substring in it over alphabet
Σ = {0, 1}.

We will design a Finite Automaton (FA) for the language:

L = { w ∈ {0,1}* | w does not contain "00" as a substring }

Explanation:

The FA must reject any string that contains "00" as a substring. So, it should accept strings
like: ε (empty string), 0, 1, 01, 101, 10101

But reject: 00, 100, 0001

18 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

States:

 q0 = Start state, where no violation has occurred.

 q1 = Last symbol was a 0, waiting to check if next is also a 0.

 q2 = Trap (Dead) state, where "00" has occurred.

This FA accepts all strings that do not contain "00" as a substring.

It enters q2 permanently on encountering "00".

Transition Table:

Current State Input 0 Input 1

→ *q0 q1 q0

→ *q1 qd q0

qd qd qd

Example 2.1.9 Construct DFA for the language of all strings that begin and end with same
symbol over the alphabet Σ = {0, 1}.

This DFA checks whether the first and last symbol of the string are the same.

 If the string starts with 0, it must end with 0.

 If it starts with 1, it must end with 1.

 If the string has only one symbol (0 or 1), it's accepted.

 Empty string ε is not accepted.

19 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

We track the first symbol and then wait to see the last symbol. So, we accept only if:

 Start and end are both 0, or

 Start and end are both 1.

Transition Table:

State 0 1

→ q0 q1 q2

q1 q3 q1

q2 q2 q4

*q3 q3 q1

*q4 q2 q4

Input: 0110

 q0 → (0) → q1

 q1 → (1) → q3

 q3 → (1) → q3

 q3 → (0) → q3

Ends in q3 → Rejected

Example 2.1.10 Construct a DFA to accept strings ending with 10.

20 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

The DFA accepts strings over Σ = {0, 1} that end with 10. This means the machine must
recognize when the last two symbols are exactly 1 followed by 0.

Transition Table:

Current State Input 0 Input 1

→ q0 q0 q1

q1 q2 q1

*q2 q0 q1

Working Example: Input: 1010

1. q0 — 1 → q1

2. q1 — 0 → q2

3. q2 — 1 → q1

4. q1 — 0 → q2

Ends in q2, so accepted.

Example 2.1.11 Construct a DFA accepting the following languages over the alphabet {a, b}.

i) Set of all strings that begin with the substring ab.

The string must start with exactly ab, and anything can follow afterward (even empty).

States:

 q0: Start state

 q1: Saw a

 q2: Saw ab → Accepting state

21 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

 qD: Any invalid start (like b or aa, etc.)

Transition Table:

Current State Input a Input b

→ q0 q1 qd

q1 qd q2

*q2 q2 q2

qd qd qd

Example:

 ab → q0 → q1 → q2 (Accepted)

 abaabb → q0 → q1 → q2 → q2 → q2 → q2

 ba → q0 → qD (Rejected)

ii) Set of all strings with at most two consecutive b’s.

The DFA should reject any string that has three or more b's in a row (bbb, abbb, etc.).

States:

 q0: No consecutive b’s yet

 q1: Saw 1 consecutive b

 q2: Saw 2 consecutive b’s

 q3: Saw 3 or more consecutive b’s → Trap state

22 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

Transition Table:

Current State Input a Input b

→ *q0 q0 q1

*q1 q0 q2

*q2 q0 q3

q3 q3 q3

Example:

 abbab → q0 → q1 → q2 → q0 → q1 (Accepted)

 abbb → q0 → q1 → q2 → q3 (Rejected)

Example 2.1.12 Construct DFA for checking "whether a string over alphabet {a, b} contains a
substring aba".

We are to construct a DFA that accepts all strings over {a, b} which contain "aba" as a
substring. That means once the substring "aba" is found anywhere in the input, the string
should be accepted.
23 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

Transition Table:

State a b

→ q0 q1 q0

q1 q1 q2

q2 q3 q0

*q3 q3 q3

Input: bbabaabb

 q0 → b → q0
 q0 → b → q0
 q0 → a → q1
 q1 → b → q2
 q2 → a → q3
 q3 → a → q3
 q3 → b → q3
 q3 → b → q3 (Accepted, since we reached final state q3).

Example 2.1.13 Design a DFA which accepts a binary number divisible by 4.

We are designing a DFA that accepts binary numbers divisible by 4. A binary number is
divisible by 4 if its last two digits are 00 (except for 0 itself).

DFA Transition Table (Input alphabet: {0, 1})

24 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

State 0 1

q0 q0 q1

q1 q2 q3

q2 q0 q1

q3 q2 q3

 q0: Remainder 0 → divisible by 4

 q1: Remainder 1

 q2: Remainder 2

 q3: Remainder 3

Input: 100

 q0 → 1 → q2

 q2 → 0 → q2

 q2 → 0 → q2

 Not accepted

Example (Binary: 100) → Decimal = 4

 q0 → 1 → q1

 q1 → 0 → q2

 q2 → 0 → q0

Final state = q0 → Accepted

Example 2.1.14 Design a DFA (Deterministic Finite Automata) that reads strings made up of
the letters in the word ‘UNIVERSITY’ and recognizes those strings that contain the word
‘UNITY’ as a substring.

We are to design a DFA over the alphabet {U, N, I, V, E, R, S, T, Y} which accepts strings
containing the substring "UNITY".
25 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

The DFA will transition through intermediate states on reading each character of the substring
"UNITY" and reach a final (accepting) state once the substring has been completely read.

Transition Table:

Current State Input Next State

→ q0 U q1

q0 ≠U q0

q1 N q2

q1 U q1

q1 ≠N,U q0

q2 I q3

q2 U q1

q2 ≠I,U q0

q3 T q4

q3 U q1

q3 ≠T,U q0

q4 Y q5 (final)

q4 U q1

q4 ≠Y,U q0

*q5 (final) Any q5

Note:

 ≠X means any character in the alphabet that is not X.

 Once we reach q5, we stay there since the string contains "UNITY".
26 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

Example: Input: "VERSUNITYTOP"

 q0 → V → q0

 q0 → E → q0

 q0 → R → q0

 q0 → S → q0

 q0 → U → q1

 q1 → N → q2

 q2 → I → q3

 q3 → T → q4

 q4 → Y → q5 (final)

 Remaining letters → q5 → q5

Accepted, as "UNITY" appears in the string.

2.2 Non-Deterministic Finite Automata (NFA)

A Non-Deterministic Finite Automaton (NFA) is a type of finite automaton where:

For a given state and input symbol, the automaton can move to zero, one, or multiple next
states.
27 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

In contrast to a Deterministic Finite Automaton (DFA), where only one unique next state is
allowed for each input from a state.

Formal Definition (5-tuple):

An NFA is defined as: M = (Q, Σ, δ, q₀, F)

Where:

 Q = Set of states

 Σ = Input alphabet (e.g., {0,1})

 δ = Transition function, where:

δ: Q × (Σ ∪ {ε}) → P(Q) (returns a set of states instead of a single state)

 q₀ = Start state

 F = Set of final states

Difference between DFA and NFA:

Feature DFA (Deterministic FA) NFA (Non-Deterministic FA)

Transition for each Exactly one transition for Zero, one or more transitions
symbol every symbol from a state allowed

Epsilon (ε) Not allowed Allowed (can change state without

transitions input)

Next state Only one possible next state Can have multiple possible next
states

Computation Single path of execution for Multiple paths can be followed

an input string simultaneously

Acceptance of string Accepted if the only path Accepted if any one path ends in
ends in final state final state

Transition function δ: Q × Σ → Q δ: Q × (Σ ∪ {ε}) → P(Q)

Speed of execution Generally faster due to single May explore many paths
path (conceptually slower)
28 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

Ease of construction May require more states Can be simpler with fewer states

Conversion Already deterministic Can be converted to DFA using

subset construction

Used in real Yes, DFAs are preferred for Not used directly, but useful for
compilers? implementation design & theory

Example 2.2.1 An NFA with states 1-5 and input alphabet {a, b} has following transition table.

q 𝛿 (q, a) 𝛿 (q, b)
→1 {1, 2} {1}
2 {3} {3}
3 {4} {4}
4 {5} ∅
*5 ∅ {5}

i) Draw transition diagram. ii) Calculate 𝛿* (1, ab). iii) Calculate 𝛿* (1, abaab)

i) Transition Diagram

ii) δ*(1, ab)

We compute extended transition function step-by-step.

 Start at state 1

 On input a: δ(1, a) = {1, 2}

Now process b from both states in {1, 2}:

 δ(1, b) = {1}

 δ(2, b) = {3}

So: δ*(1, ab) = {1, 3}

29 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

iii) δ*(1, abaab)

We compute step-by-step:

Step 1: δ(1, a) = {1, 2}

Now from {1, 2}, on input b:

 δ(1, b) = {1}

 δ(2, b) = {3}

So:
→ After ab: {1, 3}

Next input: a

 δ(1, a) = {1, 2}

 δ(3, a) = {4}

So:
→ After aba: {1, 2, 4}

Next input: a

 δ(1, a) = {1, 2}

 δ(2, a) = {3}

 δ(4, a) = {5}

So:
→ After abaa: {1, 2, 3, 5}

Final input: b

 δ(1, b) = {1}

 δ(2, b) = {3}

 δ(3, b) = {4}

 δ(5, b) = {5}

So: δ(1, abaab) = {1, 3, 4, 5}*

30 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

2.3 Epsilon - NFA

An ε-NFA (Epsilon Non-Deterministic Finite Automaton) is a type of NFA that allows

transitions without consuming any input symbol — these transitions are called epsilon (ε)
transitions.

 In this NFA with ε, q0 is a start state with input 0.

 Initially with input 0, we can go to q0 or q1.
 Similarly with input 1, we can go to state q1 or q2.

Thus, it is not definite that on input 1 whether we will be in state q 1 or q2. Hence it is called
non-deterministic finite automaton (NFA) and since there are some ε moves to simply change
the states, it is called NFA with ε.

Formal Definition of ε-NFA (Epsilon-NFA):

An ε-NFA (Epsilon Non-Deterministic Finite Automaton) is a 5-tuple:

M = (Q, Σ, δ, q0, F), where:

 Q: Finite set of states

 Σ: Input alphabet

 δ: Transition function, defined as δ: Q × (Σ ∪ {ε}) → 2Q

This means from a state, on an input symbol or ε (epsilon), the machine can move to a set of
states

 q0 ∈ Q: Start state

 F ⊆ Q: Set of final (accepting) states

In simple words: An ε-NFA is like an NFA that also allows free transitions (ε-moves),
meaning it can change states without reading any input symbol.
31 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

Example 2.3.1 Construct NFA with ε that accepts a language consisting the strings of any
number of a’s followed by any number of b’s. Followed by any number of c’s.

We are given the task to construct an ε-NFA (NFA with epsilon transitions) for the language:

L = { aⁿ bᵐ cᵒ | n, m, o ≥ 0 }

That is: any number of as (including 0), followed by any number of bs, followed by any number
of c’s.

We divide the NFA into 3 parts using ε-transitions:

1. Part that loops on a

2. Part that loops on b

3. Part that loops on c

We connect these parts using ε-moves to allow smooth switching between groups without
consuming any input.

States:

Let’s define 3 states:

 q0 → initial state (also handles a’s)

 q1 → handles b’s

 q2 → handles c’s

Transition Table:

State Input = a Input = b Input = c Input = ε

q0 {q0} ∅ ∅ {q1}

q1 ∅ {q1} ∅ {q2}
32 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

q2 ∅ ∅ {q2} ∅

Comparison between NFA and ε-NFA

Feature NFA ε-NFA

Transitions Only on input symbols On input symbols and on ε (epsilon)

ε-transitions allowed? Not allowed Allowed (move without input)

Moves without No Yes

consuming input

Construction simplicity Moderate Often simpler due to flexible

transitions

Equivalence with DFA Equivalent Equivalent (can convert to DFA)

2.4 Epsilon-Closure (ε-Closure)

The ε-closure (epsilon-closure) of a state q in an ε-NFA is:

The set of all states reachable from q by taking zero or more ε-transitions (i.e., moves
without consuming any input symbol).

The epsilon closure is as mentioned below −

 ε-closure (P) = P, where P ∈ Q

 If there exists ε-closure (P) = {q} and δ (q, ε) = r then, ε-closure (P) = {q, r}

Example 2.4.1 Find ε-closure for the following non-deterministic finite automata (NFA) with
epsilon.

ε-closure (q0) = {q0, q1, q2} means self-state + ε – reachable states.

ε-closure (q1) = {q1, q2} means q1 is a self-state and q2 is a state obtained from q1 with ε
input.
33 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

ε-closure (q2) = {q2}

2.5 Conversion of NFA with ε to NFA without ε

To convert an ε-NFA (NFA with epsilon transitions) into a regular NFA (without ε transitions),
follow these steps:

Step 1: Compute ε-closure for each state:

 For every state qi ∈ Q, find its ε-closure, denoted as:

ε-closure(qi)

This includes all the states reachable from qi using only ε-transitions.

2. Construct new transition function δ′:

 For each input symbol a ∈ Σ and for each state q ∈ Q, calculate the new transition:

δ (q, a) = ε-closure(δ(δ(q, ε), a))

where: δ(q, ε) = ε-closure(q)

This means:

o First, compute ε-closure of q.

o Then, from all those states, apply input a using the original δ

o Finally, take ε-closure of the resulting states

3. Repeat step 2 for all input symbols and all states:

 Apply the process for each symbol in the alphabet and each state in the NFA.

4. Build the new transition table:

 Use the results from step 3 to create a transition table for the equivalent NFA without
ε-transitions.

Example 2.5.1 Convert the given NFA with ε to NFA without ε.

34 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

We first find out ε-closure of each state.

ε-closure (q0) = {q0, q1, q2}

ε-closure (q1) = {q1, q2}

ε-closure (q2) = {q2}

Now, we obtain δ’ transitions for each state on each input symbol.

δ’ (q0, a) = ε-closure(δ(δ(q0, ε), a))

= ε-closure (δ (ε-closure(q0), a))

= ε-closure (δ (q0, q1, q2), a)

= ε-closure (δ (q0, a) ∪ δ (q1, a) ∪ δ (q2, a))

= ε-closure (q0 ∪ ∅ ∪ ∅)

= ε-closure (q0)

= {q0, q1, q2}

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

= ε-closure (δ (q0, q1, q2), b)

= ε-closure (δ (q0, b) ∪ δ (q1, b) ∪ δ (q2, b))

= ε-closure (∅ ∪ q1 ∪ ∅)

= ε-closure (q1)

= {q1, q2}

δ’ (q0, c) = ε-closure(δ(δ(q0, ε), c))

= ε-closure (δ (q0, q1, q2), c)

= ε-closure (δ (q0, c) ∪ δ (q1, c) ∪ δ (q2, c))

35 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

= ε-closure (∅ ∪ ∅ ∪ q2)

= ε-closure (q2)

= {q2}

δ’ (q1, a) = ε-closure(δ(δ(q1, ε), a))

= ε-closure (δ (ε-closure(q1), a)

= ε-closure (δ (q1, q2), a)

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

= ε-closure (∅ ∪ ∅)

= ε-closure (∅)

=∅

δ’ (q1, b) = ε-closure(δ(δ(q1, ε), b))

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

= ε-closure (δ (q1, q2), b))

= ε-closure (δ (q1, b) ∪ δ (q2, b))

= ε-closure (q1 ∪ ∅)

= ε-closure (q1)

= {q1, q2}

δ’ (q1, c) = ε-closure(δ(δ(q1, ε), c))

= ε-closure (δ (ε-closure(q1), c))

= ε-closure (δ (q1, q2), c))

= ε-closure (δ (q1, c) ∪ δ (q2, c))

= ε-closure (∅ ∪ q2)

= ε-closure (q2)

= {q2}
36 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

δ’ (q2, a) = ε-closure(δ(δ(q2, ε), 0))

= ε-closure (δ (ε-closure(q2), 0))

= ε-closure (δ (q2, 0))

= ε-closure (∅)

=∅

δ’ (q2, b) = ε-closure(δ(δ(q2, ε), b))

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

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

= ε-closure (∅)

=∅

δ’ (q2, c) = ε-closure(δ(δ(q2, ε), c))

= ε-closure (δ (ε-closure(q2), c))

= ε-closure (δ (q2, c))

= ε-closure (q2)

= {q2}

Final Transition Table for NFA (without ε)

State Input a Input b Input c

q0 {q0, q1, q2} {q1, q2} {q2}

q1 ∅ {q1, q2} {q2}

q2 ∅ ∅ {q2}

The NFA without ε can be shown as:

37 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

Example 2.5.2 Convert the following NFA with ε-moves into NFA without ε moves.

We compute ε closures of A, B, C, D

ε-closure (A) = {A, B, C}

ε-closure (B) = {B}

ε-closure (C) = {C}

ε-closure (D) = {D}

The δ’ transitions on each input symbol are

δ’ (A, 0) = ε-closure(δ(δ(A, ε), 0))

38 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

= ε-closure (δ (ε-closure(A), 0))

= ε-closure (δ (A, B, C), 0))

= ε-closure (δ (A, 0) ∪ δ (B, 0) ∪ δ (C, 0))

= ε-closure (A ∪ D ∪ C)

= {A, B, C, D}

δ’ (A, 1) = ε-closure(δ(δ(A, ε), 1))

= ε-closure (δ (ε-closure(A), 1))

= ε-closure (δ (A, B, C), 1))

= ε-closure (δ (A, 1) ∪ δ (B, 1) ∪ δ (C, 1))

= ε-closure (∅ ∪ B ∪ D)

= {B, D}

δ’ (B, 0) = ε-closure(δ(δ(B, ε), 0))

= ε-closure (δ (ε-closure(B), 0))

= ε-closure (δ (B, 0))

= ε-closure (D)

= {D}

δ’ (B, 1) = ε-closure(δ(δ(B, ε), 1))

= ε-closure (δ (ε-closure(B), 1))

= ε-closure (δ (B, 1))

= ε-closure (B)

= {B}

δ’ (C, 0) = ε-closure(δ(δ(C, ε), 0))

= ε-closure (δ (ε-closure(C), 0))

= ε-closure (δ (C, 0))

39 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

= ε-closure (C)

= {C}

δ’ (C, 1) = ε-closure(δ(δ(C, ε), 1))

= ε-closure (δ (ε-closure(C), 1))

= ε-closure (δ (C, 1))

= ε-closure (D)

= {D}

δ’ (D, 0) = ε-closure(δ(δ(D, ε), 0))

= ε-closure (δ (ε-closure(D), 0))

= ε-closure (δ (D, 0))

= ε-closure (∅)

= {∅}

δ’ (D, 0) = ε-closure(δ(δ(D, ε), 1))

= ε-closure (δ (ε-closure(D), 1))

= ε-closure (δ (D, 1))

= ε-closure (∅)

= {∅}

Final Transition Table for NFA (without ε)

State Input 0 Input 1

A {A, B, C, D} {B, D}

B {D} {B}

C {C} {D}

D ∅ ∅

The NFA without ε can be shown as:

40 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

2.6 NFA to DFA Conversion

To convert a Non-Deterministic Finite Automaton (NFA) into an equivalent Deterministic

Finite Automaton (DFA), we follow a method called subset construction or powerset
construction.

Let the given NFA be:

 M = (Q, Σ, δ, q₀, F) where:

o Q = Set of states

o Σ = Input alphabet

o δ = Transition function

o q₀ = Start state

o F = Set of final states

We want to construct an equivalent DFA:

 M' = (Q', Σ', δ', q₀', F') such that L(M) = L(M')

Conversion Steps:

1. Start State: The start state of the DFA (q₀') will be the same as the start state of the NFA
(q₀), but represented as a set: q₀' = {q₀}. Add this to the set of DFA states Q'.

2. Transition Construction: For each state S = {q₁, q₂, ..., qᵢ} in Q' and for each input symbol
'a' in Σ:
41 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

i) Compute the union of transitions from each state on input 'a':

δ' (S, a) = δ (q₁, a) ∪ δ (q₂, a) ∪ ... ∪ δ (qᵢ, a)

ii) Let the resulting set of states be T = {q₁, q₂, ..., qₖ}. If T isn’t already in Q’, add it to Q’.

iii) Repeat this process for each newly added state and for each symbol in Σ until no new
states are generated.

3. Final States: Any DFA state S = {q₁, q₂, ..., qₙ} will be a final state in DFA (i.e., in F’) if
at least one qi ∈ F (final states of NFA).

Example 2.6.1 Convert following NFA into its equivalent DFA.

States (Q) Input 0 Input 1

→P P, Q R
Q R R
R S Q
*S S S

δ (P, 0) = {P, Q} = [P, Q] (New state)

δ (P, 1) = {R} = [R]

δ (Q, 0) = {R} = [R]

δ (Q, 1) = {R} = [R]

δ (R, 0) = {S} = [S]

δ (R, 1) = {R} = [R]

δ (S, 0) = {P, Q} = [P, Q] (New state)

δ (S, 1) = {R} = [R]

The δ transitions can be applied on new state [P, Q].

δ [(P, Q), 0] = {P, Q, R} = [P, Q, R] (New state)

δ [(P, Q), 1] = {R} = [R]

δ [(P, Q, R), 0] = {P, Q, R} = [P, Q, R, S] (New state)

δ [(P, Q, R), 1] = {R, Q} = [R, Q] (New state)

42 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

δ [(R, Q), 0] = {R, S} = [R, S] (New state)

δ [(R, Q), 1] = {R, Q} = [R, Q]

δ [(R, S), 0] = {S} = [S]

δ [(R, S), 1] = {Q, S} = [R, S]

δ [(Q, S), 0] = {R, S} = [R, S]

δ [(Q, S), 1] = {R, S} = [R, S]

As no new state is getting generated, we will stop applying δ transitions. The transition table
for DFA is as follows:

States (Q) Input 0 Input 1

[P] [P, Q] [R]
[Q] [R] [R]
[R] [S] [Q]
*[S] [S] [S]
[P, Q] [P, Q, R] [R]
[P, Q, R] [P, Q, R, S] [R, Q]
*[P, Q, R, S] [P, Q, R, S] [R, Q, S]
[R, Q] [R, S] [R, Q]
*[R, Q, S] [R, S] [R, Q, S]
*[R, S] [S] [Q, S]
*[Q, S] [R, S] [R, S]

Example 2.6.2 Convert DFA equivalent to the given NFA.

State Input 0 Input 1

→ [p] {p, q} p
q r r
r s -
*s s s

The NFA: M = {{p, q, r, s}, {0, 1}, δ {p}, {s}}

The equivalent DFA will be constructed.

43 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

States (Q) Input 0 Input 1

→ [p] {p, q} p
q r r
r s -
*s s s
[p, q] [p, q, r] [p, r]
[p, q, r] [p, q, r, s] [p, r]
[p, r] [p, q, s] [p]
*[p, q, r, s] [p, q, r, s] [p, r, s]
*[p, q, s] [p, q, r, s] [p, r, s]
*[p, r, s] [p, q, s] [p, s]
*[p, s] [p, q, s] [p, s]

Final State F’ = { [s], [p, q, r, s], [p, q, s], [p, r, s], [p, s] }

The transition graph shows two disconnected parts. But part 1 will be accepted as final DFA
because it consists of start state and final states, in part 2 there is no start state.

2.7 Minimization of DFAs

44 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

The minimization of a Finite State Machine (FSM) means reducing the number of states in a
given FA without changing the language it accepts.

While minimizing an FSM, we first identify equivalent states — states that behave identically
for all input strings — and then represent them using a single representative state.

Equivalent States

Two states q₁ and q₂ are equivalent if, for every string x ∈ Σ*:

 Both δ(q₁, x) and δ(q₂, x) lead to final states, OR

 Both lead to non-final states.

Here, Σ* means any string of any length over the alphabet Σ.

Method for Constructing Minimum State Automata

Step 1: Initial Partition (π0)

Create:

 Q01 = Set of all final states.

 Q02 = Q – Q01 = Set of all non-final states.

Thus:

π0 = { Q0¹ , Q0² }

Step 2: Refinement of Partitions

From πk, construct πk+1:

 Let Qik be any subset in πᵏ.

 If q₁ and q₂ belong to Qik, they are (k+1)-equivalent if:

o δ(q₁, a) and δ(q₂, a) belong to the same equivalence class in πk for all a ∈ Σ.

 Split Qik into smaller sets based on this rule to form πk+1.

Repeat this process for every subset in πᵏ to get all elements of πk+1.

Step 3: Repeat Until Stable

Continue refining:
45 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

π0 → π1 → π2 → … → πn

Stop when: πn = πn+1

(No further refinement possible.)

Step 4: Construct the Minimized DFA

 Replace all equivalent states in each final partition with a single representative state.

 Define the start and final states accordingly.

 Create transitions for the new states.

Result:
The resulting DFA has the minimum possible number of states while accepting the same
language as the original DFA.

Example 2.7.1 Construct the minimum state automaton for the following transition table.

State Input 0 Input 1

q0 q1 q0
q1 q0 q2
q2 q3 q1
q3 q3 q0
q4 q3 q5
q5 q6 q4
q6 q5 q6
q7 q6 q3

Step 2: Initial Partition π⁰

Separate final and non-final states:

Q₀¹ = { q₃ } (Final states)

Q₀² = { q₀, q₁, q₂, q₄, q₅, q₆, q₇ } (Non-final states)

π0 = { { q₃ }, { q₀, q₁, q₂, q₄, q₅, q₆, q₇ } }

Step 3: First Refinement π1

Check each state in the non-final set and split based on transitions into different groups of π 0.
46 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

 q₀: (0 → q₁ non-final), (1 → q₀ non-final) → both in Q₀² → stays.

 q₁: (0 → q₀ non-final), (1 → q₂ non-final) → stays.

 q₂: (0 → q₃ final), (1 → q₁ non-final) → split.

 q₄: (0 → q₃ final), (1 → q₅ non-final) → split.

 q₅: (0 → q₆ non-final), (1 → q₄ non-final) → stays with non-final.

 q₆: (0 → q₅ non-final), (1 → q₆ non-final) → stays with non-final.

 q₇: (0 → q₆ non-final), (1 → q₃ final) → split.

After splitting:

π1 = { { q₃ }, { q₀, q₁, q₅, q₆ }, { q₂, q₄, q₇ } }

Step 4: Second Refinement π²

Check each new group:

1. { q₀, q₁, q₅, q₆ }:

o q₀: (0 → q₁ same group), (1 → q₀ same group) → stays.

o q₁: (0 → q₀ same), (1 → q₂ diff group) → split.

o q₅: (0 → q₆ same), (1 → q₄ diff) → split.

o q₆: (0 → q₅ same), (1 → q₆ same) → stays.

Split into:

o { q₀, q₆ }

o { q₁, q₅ }

2. { q₂, q₄, q₇ }:

o q₂: (0 → q₃ final), (1 → q₁ in { q₁, q₅ }) → same pattern as q₄ → same group.

o q₄: (0 → q₃ final), (1 → q₅ in { q₁, q₅ }) → same pattern as q₂ → same group.

o q₇: (0 → q₆ in { q₀, q₆ }), (1 → q₃ final) → different → split.

Split into:
47 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

o { q₂, q₄ }

o { q₇ }

So

π2 = { { q₃ }, { q₀, q₆ }, { q₁, q₅ }, { q₂, q₄ }, { q₇ } }

Step 5: Check for further refinement

 All states in each group behave identically → no further split.

So:

π2 = π3 → STOP

Minimized Transition Table

State Input 0 Input 1

→ [q0, q6] [q1, q5] [q0, q6]
[q1, q5] [q0, q6] [q2, q4]
[q2, q4] [q3] [q1, q5]
* [q3] [q3] [q0, q6]
[q7] [q0, q6] [q3]

Transition Diagram:

3. FA with output

3.1 Moore Machine

48 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

A Moore Machine is a type of Finite State Machine (FSM) in which the output is
determined solely by the current state, not by the input symbol.

This means the output is associated with each state, and it changes only when the machine
changes its state.

Formal Definition

A Moore Machine can be represented as a 6-tuple:

M = (Q, Σ, Δ, δ, λ, q0)

Where:

 Q → Finite set of states.

 Σ → Input alphabet.

 Δ → Output alphabet.

 δ → Transition function δ: Q × Σ → Q (determines the next state).

 λ → Output function λ: Q → Δ (associates output with a state).

 q₀ → Start state (q₀ ∈ Q).

Key Characteristics

1. Output depends only on the present state (not the input).

2. Output changes only when the state changes.

3. Each state has a fixed output value.

4. Generally, has more states than an equivalent Mealy Machine.

Example

Next State
Present State Output
Σ=0 Σ=1
→ q0 1 q1 q2

q1 1 q2 q1

q2 0 q2 q0
49 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

Applications

 Sequential circuit design.

 Control systems.

 Protocol design in networking.

3.2 Mealy Machine

A Mealy Machine is a type of Finite State Machine (FSM) in which the output depends on
both the current state and the current input symbol.

Unlike a Moore Machine, the output can change immediately when the input changes, without
waiting for a state change.

Formal Definition

A Mealy Machine can be represented as a 6-tuple:

M = (Q, Σ, Δ, δ, λ, q0)

Where:

 Q → Finite set of states.

 Σ → Input alphabet.

 Δ → Output alphabet.

 δ → Transition function δ: Q × Σ → Q — determines the next state.

 λ → Output function λ: Q × Σ → Δ— output depends on both current state and input.

50 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

 q₀ → Start state (q₀ ∈ Q).

Key Characteristics

1. Output depends on current state and input.

2. Fewer states compared to an equivalent Moore Machine.

3. Output can change without a state change.

4. Often more compact and efficient.

Applications

 Real-time systems.

 Data communication protocol design.

 Sequence detectors.

Example

Present State Next State

Σ=0 Σ=1
State Output State Output
q0 q2 1 q1 0

q1 q1 0 q2 1
51 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

q2 q2 0 q0 0

3.3 Difference between Moore and Mealy Machine

Aspect Moore Machine Mealy Machine

Definition Output depends only on the Output depends on both current

current state. state and current input.

Output Function λ: Q → Δ λ: Q × Σ → Δ

Output Change Output changes only on state Output can change immediately
change. with input change (even without
state change).

State Diagram State labeled as State / Output. Transition labeled as Input /

Notation Output.

Number of States Usually more states are Usually fewer states are
required. required.

Speed of Output Slower, because output changes Faster, because output depends
after state transition. directly on input.

Design Complexity Easier to design and understand. Slightly more complex to design.

Applications Control systems, vending Sequence detectors, real-time

machines. systems.

Example 3.3.1 Design a Moore Machine to generate 1’s complement of a given binary
number.

What is 1's Complement?

It is the binary number obtained by flipping each bit:

 0→1

 1→0

A Moore machine outputs depend only on the current state.

We design a machine that:
52 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

 Reads each input bit (0 or 1),

 Goes to a state that gives output 1 for input 0, and output 0 for input 1.

Transition Table:

State Input 0 Input 1 Output

q0 q1 q2 0

q1 q1 q2 1

q2 q1 q2 0

 q0: Initial state

 q1: For input 0, gives output 1

 q2: For input 1, gives output 0

Example: Input: 1010

1. Start at q0

2. Input = 1: q0 → q2, output = 0

3. Input = 0: q2 → q1, output = 1

4. Input = 1: q1 → q2, output = 0

5. Input = 0: q2 → q1, output = 1

Final Output: 0101, which is the 1's complement of 1010.

53 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

Example 3.3.2. Design a Mealy Machine to find 2’s complement of a given binary number.

To compute the 2’s complement of a binary number using a Mealy machine, follow this
logic:

 Traverse the binary number from right to left.

 Copy all bits unchanged until the first 1 is found (this 1 is kept as-is).

 After that first 1, invert all remaining bits (0→1, 1→0).

States Description:

 q0: Initial state – looking for the first 1 from right to left.

 q1: After finding the first 1 – start inverting bits.

Transition Table

Current State Input 0 Input 1

q0 q0/0 q1/1

q1 q1/1 q1/0

3.4 Conversion of Moore Machine to Mealy Machine

Let M = (Q, Σ, Δ, δ, λ, q0) be a Moore machine.

The equivalent Mealy machine can be represented as: M’ = (Q, Σ, Δ, δ, λ, q0).

The output function λ' can be obtained as: λ' (q, a) = λ (δ(q, a))

Meaning: The Mealy Machine’s output for a given state and input is the output of the
destination state in the Moore Machine.
54 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

Example 3.4.1 Consider the Moore Machine described by the transition table given below.
Construct corresponding Mealy Machine.

Next State
Present State Output
Σ=0 Σ=1
→ q1 0 q1 q2

q2 0 q1 q3

q3 1 q1 q3

The output function λ' can be obtained using following rule

λ' (q1, 0) = λ (δ (q1, 0))

= λ (q1)

=0

λ' (q1, 1) = λ (δ (q1, 1))

= λ (q2)

=0

λ' (q2, 0) = λ (δ (q2, 0))

= λ (q1)

=0
55 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

λ' (q2, 1) = λ (δ (q2, 1))

= λ (q3)

=1

λ' (q3, 0) = λ (δ (q3, 0))

= λ (q1)

=0

λ' (q3, 1) = λ (δ (q3, 1))

= λ (q3)

=1

The transition table for Mealy Machine can be created as follows:

Present State Next State

Σ=0 Σ=1
State Output State Output
q1 q1 0 q2 0

q2 q1 0 q3 1

q3 q1 0 q3 1
56 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

3.5 Conversion of Moore Machine to Mealy Machine

Let M = (Q, Σ, Δ, δ, λ, q0) be a Mealy Machine.

Then there exists an equivalent Moore Machine: M′ = (Q×Δ, Σ, Δ, δ′, λ′, [q0, b0])

where b0 is an output symbol selected from Δ.

Definition of Functions

1. Transition Function: δ′ ([q, b], a) = [δ (q, a), λ (q, a)]

This defines the move made by M′ on input a.

It transitions to the next state based on the original Mealy state and updates the output
component.

2. Output Function: λ′ ([q, b]) = b

This defines the output produced for the corresponding Moore state.

Meaning

 In Moore, the output is linked to states, so we form new states as pairs [q, b], where:

o q → Original Mealy state

o b → Output that should be produced in that state

/
 For each Mealy transition 𝑞 𝑝, we create a Moore transition from [q, b′] to [p, b],
where b′ is the output of the source state.

Procedure

1. Identify all transitions in the Mealy Machine.

/
2. For each transition 𝑞 𝑝, create a Moore state [p, b] if it does not already exist.

3. Construct the transition table for δ′ using: δ′ ([q, b], a) = [δ (q, a), λ (q, a)]

4. Assign outputs to states using: λ′ ([q, b]) = b

5. Repeat until all states and transitions are processed.

Example 3.5.1 Convert the following Mealy machine into equivalent Moore Machine.
57 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

We first write the transition table for the given transition graph:

Present State Input 0 Output Input 1 Output

q0 q1 N q2 N
q1 q1 Y q2 N
q2 q1 N q2 Y

Now we will find out the states and corresponding outputs for Moore machine. The states for
Moore machine will be:

[q0, N], [q0, Y], [q1, N], [q1, Y], [q2, N], [q2, Y]

Now, we calculate δ′ and λ′ for all the above given states:

δ′ ([q0, N], 0) = [δ (q0, 0), λ (q0, 0)]

= [q1, N]

λ′ (q0, N) = N

δ′ ([q0, N], 1) = [δ (q0, 1), λ (q0, 1)]

= [q2, N]

λ′ (q0, N) = N

δ′ ([q0, Y], 0) = [δ (q0, 0), λ (q0, 0)]

= [q1, N]
58 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

λ′ (q0, Y) = Y

δ′ ([q0, Y], 1) = [δ (q0, 1), λ (q0, 1)]

= [q2, N]

λ′ (q0, Y) = Y

δ′ ([q1, N], 0) = [δ (q1, 0), λ (q1, 0)]

= [q1, Y]

λ′ (q1, N) = N

δ′ ([q1, N], 1) = [δ (q0, 1), λ (q0, 1)]

= [q2, N]

λ′ (q1, N) = N

δ′ ([q1, Y], 0) = [δ (q1, 0), λ (q1, 0)]

= [q1, Y]

λ′ (q1, Y) = Y

δ′ ([q1, Y], 1) = [δ (q1, 0), λ (q1, 0)]

= [q2, N]

λ′ (q1, Y) = Y

δ′ ([q2, N], 0) = [δ (q2, 0), λ (q2, 0)]

= [q1, N]

λ′ (q1, N) = N

δ′ ([q2, N], 1) = [δ (q2, 1), λ (q2, 1)]

= [q2, Y]

λ′ (q2, N) = N

δ′ ([q2, Y], 0) = [δ (q2, 0), λ (q2, 0)]

= [q1, N]
59 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

λ′ (q2, Y) = Y

δ′ ([q2, Y], 1) = [δ (q2, 0), λ (q2, 0)]

= [q2, Y]

λ′ (q2, Y) = Y

Next State
Present State Output
Σ=0 Σ=1
[q0, N] N [q1, N] [q2, N]

[q0, Y] Y [q1, N] [q2, N]

[q1, N] N [q1, Y] [q2, N]

[q1, Y] Y [q1, Y] [q2, N]

[q2, N] N [q1, N] [q2, Y]

[q2, Y] Y [q1, N] [q2, Y]

Q. Justify that there can be the equivalent Mealy machine for any Moore machine by suitable
example.

Yes, for every Moore machine, there exists an equivalent Mealy machine.

 A Moore machine produces output on states.

 A Mealy machine produces output on transitions.

To convert a Moore machine to a Mealy machine, we shift the output from states to
the incoming transitions based on the state the transition leads to.
60 | P a g e © Haris Chaus 2025 | ALL RIGHTS ARE RESERVED as per Copyright Act, 1957.

Example – Moore Machine

State Input = 0 Input = 1 Output
A B C 0
B B D 1
C D C 0
D D D 1

 Output is based on the state only.

Equivalent Mealy Machine

To convert it: The output will now be on transitions depending on the next state’s output.

State Input = 0 Input = 1

A B/1 C/0
B B/1 D/1
C D/1 C/0
D D/1 D/1

Explanation:
 From state A:
o On input 0 → goes to B → B has output 1 → so transition is B/1
o On input 1 → goes to C → C has output 0 → so transition is C/0
 And so on for others.
The behavior/output of both machines is the same, just represented differently. Hence,
every Moore machine can be converted to an equivalent Mealy machine.