UNIT 1 : BASIC CONCEPTS OF FINITE AUTOMATA

 Importance of TCS, Alphabets, Strings, Languages, Closure properties, Finite

Automata (FA) and Finite State machine (FSM).

 Deterministic Finite Automata (DFA) and Nondeterministic Finite Automata

(NFA): Definitions, transition diagrams and Language recognizers, Equivalence

between NFA with and without ε- transitions, NFA to DFA Conversion,

Minimization of DFA, FSM with output: Moore and Mealy machines,

Applications and limitations of FA.

TCS : UNIT 1 1
 INTRODUCTION TO FINITE AUTOMATA

 Finite Automata(FA) is the simplest machine to recognize

patterns.
 The finite automata or finite state machine is an abstract
machine that has five elements or tuples.
 It has a set of states and rules for moving from one state
to another but it depends upon the applied input symbol.
Basically, it is an abstract model of a digital computer.
 INTRODUCTION TO FINITE AUTOMATA

 Finite automata machine takes the string of symbol as input and changes its state
accordingly.
 In the input, when a desired symbol is found then the transition occurs.
 While transition, the automata can either move to the next state or stay in the same state.
APPLICATIONS:

•For recognizing the pattern using regular expressions.

•For the designing of the combination and sequential circuits using Mealy and Moore Machines.

•Used in text editors.

•For the implementation of spell checkers.

•For the designing of lexical analysis of a compiler.

TCS : UNIT 1 4
 FINITE AUTOMATA
A Finite Automata consists of the following 5 elements or tuples:
Q : Finite set of states.
Σ : set of Input Symbols.
q0 : Initial state.
F : set of Final States.
δ : Transition Function.

Formal specification of machine is : { Q, Σ, q0, F, δ }

FINITE AUTOMATA

1. DFA (DETERMINISTIC FINITE AUTOMATA)

2. NFA (NONDETERMINISTIC FINITE AUTOMATA)

TCS : UNIT 1 5
 DETERMINISTIC FINITE AUTOMATA(DFA)
DFA consists of 5 tuples : {Q, Σ, q0, F, δ}.

Q : set of all states.

Σ : set of input symbols. ( Symbols which machine takes as input )

q0 : Initial state. ( Starting state of a machine )

F : set of final state.

δ : Transition Function, defined as δ : Q X Σ --> Q.

FCQ

TCS : UNIT 1 6
 DETERMINISTIC FINITE AUTOMATA

 In a DFA, for a particular input character, the machine goes to one state only.

 A transition function is defined on every state for every input symbol.

 Also in DFA null (or ε) move is not allowed, i.e., DFA cannot change state without

any input character.

For example, Prepare a DFA with Σ = {a, b} that accepts all strings starting with a.

Transition Function, defined as δ : Q X Σ --> Q

TCS : UNIT 1 7
 A Deterministic Finite Automaton (DFA) consists of a finite set of states and a set of
transitions from one state to another state on input symbols selected from an alphabet S.
 The initial state is generally denoted by q0.
 For each input symbol there is one transition for each state.
 There are one or more “final” or “accepting” states.
 The term “deterministic” says that for each input symbol, there is one and only one state to
which the automaton can transit from its current state.
 In case of “non-deterministic” FA the machine can make transit to zero or one or more
states on the same input symbol.

TCS : UNIT 1 8
 Transition Function, defined as δ : Q X Σ --> Q

One important thing to note is, there can be

many possible DFAs for a pattern. A DFA with

a minimum number of states is generally

preferred.

TCS : UNIT 1 9
 NONDETERMINISTIC FINITE AUTOMATA (NFA)

A Finite Automata(FA) is said to be non-deterministic if there is more

than one possible transition from one state on the same input symbol.

NFA consists of 5 tuples : {Q, Σ, q0, F, δ}.

Q : finite set of all states.

Σ : finite set of input symbols. ( Symbols which machine takes as input )

q0 : Initial state. ( Starting state of a machine )

F : set of final states F C Q

δ : Transition Function, defined as δ : Q X Σ --> 2Q

TCS : UNIT 1 10
• Choices of Moves In DFA :δ : Q X Σ --> Q
• Not fixed behaviour
• Nondeterministic
In NFA :δ : Q X Σ --> 2Q

• Used for Regular Language

• Designing is easy

TCS : UNIT 1 11
Dead Configuration -

In Non-Deterministic Finite Automata,

•The result of a transition function may be empty.
•In such a case, automata gets stopped forcefully after entering that configuration.
•This type of configuration is known as dead configuration.
•The string gets rejected after entering the dead configuration.

TCS : UNIT 1 12
 DFA NFA
DFA stands for Deterministic Finite Automata. NFA stands for Nondeterministic Finite Automata.

Multiple state transitions are not possible for each

symbolic representation. (i.e.For each symbolic Multiple state transitions are possible for each
representation of the alphabet, there is only one symbolic representation.
state transition.)

DFA cannot use Empty String transition. NFA can use Empty String transition.
(i.e. Є move is not allowed) (i.e. Є move is allowed)

Dead Configuration is not allowed. Dead Configuration is allowed.

δ: QxΣ -> 2Q i.e. next possible state belongs to

δ: QxΣ -> Q i.e. next possible state belongs to Q.
power set of Q.
TCS : UNIT 1 13
 DFA NFA

DFA is more difficult to construct. NFA is easier to construct.

Time needed for executing an input string is less. Time needed for executing an input string is more.

DFA requires more space. NFA requires less space then DFA.

Backtracking is allowed in DFA. Backtracking is not always possible in NFA.

Conversion of Regular expression to DFA is Conversion of Regular expression to NFA is simpler

difficult. compared to DFA.

All DFA are NFA. Not all NFA are DFA.

TCS : UNIT 1 14
 NFA TO DFA CONVERSION
Design NFA of all binary strings in which second last bit is 1. Use this NFA to construct DFA accepting the
same set of strings

TCS : UNIT 1 15
UNIVERSITY PROBLEM ON NFA TO DFA CONVERSION

(solved during theory class – refer class notes)

TCS : UNIT 1 16
 Є – NFA (NFA WITH Є TRANSITIONS)

 ∈-NFA is a part of Finite Automata.

 ∈ is a symbol that represents empty inputs.

 ∈-NFA is the representation that allows an automaton to change its state without an input, i.e. even

if the input is null the automaton can change its state.

 ∈-Non-Deterministic Finite Automata (∈- NFA) has a different transition function than regular NFA.

 In general, ∈-transitions are used when they are convenient. (For example, when constructing an

NFA from a regular expression, you start by constructing small parts of the automaton corresponding

to parts of the expression. To connect them, you need to put a transition.)

TCS : UNIT 1 17
Є- NFA consists of 5 tuples : {Q, Σ, q0, F, δ}.

Q : finite set of all states.

Σ : finite set of input symbols. ( Symbols which machine takes as input )

q0 : Initial state. ( Starting state of a machine )

F : set of final states F C Q

δ : Transition Function, defined as δ : Q X (Σ U Є) --> 2Q

(a + b + c)*

TCS : UNIT 1 18
∈-NFA for a+ : ‘a+’ means that there must be at least one ‘a’ in the input expression for it to be acceptable

It is preceded and succeeded by epsilon

because the expression may or may not
contain anything else at all. There is
epsilon feedback from state q2 to q1 so
that there can be more than one ‘a’ in the
expression.
∈-NFA for a* : ‘a*’ means that there can be any number of ‘a’ in the expression, including 0

The previous structure is just

modified a bit so that even if there is
no input symbol, i.e. if the input
symbol is null, then also the
expression is valid.

TCS : UNIT 1 19
∈-NFA for a+b : This structure accepts either a or b as input

∈-NFA for ab

TCS : UNIT 1 20
∈-NFA for L = (a+b)*bc+  L = (a+b)*bc+ can be divided into 3 parts – (a+b)* , b
and c +.
 The first part can be drawn applying the third rule and
then by applying the second rule considering a+b as
one unit.
 The third part is to be drawn by applying the first rule,
and they are just connected with a ‘b’ in between.

TCS : UNIT 1 21
 CONVERSION OF Є-NFA TO NFA
To remove the epsilon move/Null move from Є-NFA and to
convert it into NFA, we follow the steps mentioned below.

STEP-1:
Consider the two vertexes having the epsilon move. Here in we
have vertex v1 and vertex v2 having epsilon move from v1 to v2.
STEP-2:
Now find all the moves to any other vertex that start from vertex
v2 (other than the epsilon move that is considering).
After finding the moves, duplicate all the moves that start from
vertex v2, with the same input to start from vertex v1 and remove
the epsilon move from vertex v1 to vertex v2.
STEP-3:
See that if the vertex v1 is a initial (start) state or not. If vertex v1 is
a start state, then we will also make vertex v2 as a start state. If
vertex v1 is not a start state, then there will not be any change.

TCS : UNIT 1 22
STEP-4:
See that if the vertex v2 is a final state or not.
If vertex v2 is a final state, then we will also make vertex v1 as a final state.
If vertex v2 is not a final state, then there will not be any change.
Repeat the steps(from step 1 to step 4) until all the epsilon moves are removed from the NFA.

STEP-2
OUTPUT

TCS : UNIT 1 23
 STEP-4
STEP-3
OUTPUT
OUTPUT

TCS : UNIT 1 24
Transition table for Є-NFA is: Transition table for NFA without Є
is:

States/Input Input 0 Input 1

States/Inpu Input
Input 0 Input 1
t epsilon
q0 q3 q1,q4
q0 – q1 q2
q1 – q0
q1 – q0 –

q2 q3 q4
q2 q3 q4 –

q3 q2 –
q3 q2 – –

q4 q2 – – q4 q2 –

TCS : UNIT 1 25
Convert Ԑ NFA to NFA without Ԑ transition

Soln 

TCS : UNIT 1 26
Convert diagram below to NFA without Ԑ transition

TCS : UNIT 1 27
 MINIMIZATION OF DFA
Construct a minimum state automata equivalent to given
automata ?

TCS : UNIT 1 28
Step 01: Remove steps which are unreachable from initial states.

TCS : UNIT 1 29
Step 02: Split All states into two groups
group of non final states & group of final states
A0 = {q0, q1, q2}
A1 = {q3, q4, q5}
Zero Equivalent class π0 = {q0, q1, q2} {q3, q4, q5}
A01 = {q0} A02 = { q1, q2}
A11 = {q3} A12 = {q4, q5}
First Equivalent class π1 = {q0} { q1, q2} {q3} {q4, q5}
A01 & A11 cannot be further partitioned
A02 = { q1, q2} equivalent is same group
A12 = {q4, q5} equivalent is same group
Second Equivalent classπ2 = {q0} { q1, q2} {q3} {q4, q5}
π2 = π1
TCS : UNIT 1 30
π2 = {q0} { q1, q2} {q3} {q4, q5}

TCS : UNIT 1 31
Construct a minimum state automata equivalent to given automata ?

Transition table for above automata.

State Input = a Input = b

->q0 Initial q1 q3
state
q1 q2 q4
q2 q1 q1
q3 q2 q4
q4 Final q4 q4
state

π0 = {q4}, {q0,q1,q2,q3} In minimized DFA, we have three

π1 = {q4}, {q0,q2}, states,
{q1,q3} 1.{q4},
π2 = {q4}, {q0,q2}, 2.{q0,q2},

{q1,q3} 3.{q1,q3}

π2 = π1 TCS : UNIT 1 32
State Input = a Input = b
->{q0,q2} Initial {q1,q3} {q1,q3}
state

{q1,q3} {q0,q2} {q4}

{q4} Final state {q4} {q4}

TCS : UNIT 1 33
 FSM WITH OUTPUT: MOORE MACHINE
Moore machines are finite state machines with output value and its output depends only
on present state.
It can be defined as 6 tuples (Q, ∑, q0, δ, Δ, λ) where:

Q : set of all states.

Σ : set of input symbols. ( Symbols which machine takes as input )

q0 : Initial state. ( Starting state of a machine )

δ : Transition Function, defined as δ : Q X Σ --> Q

Δ: set of output symbols

λ : Output Function, defined as λ : Q --> Δ

TCS : UNIT 1 34
Current State Next State Output
Input = 0 Input = 1
q0 q0 q1 a
q1 q2 q0 b
q2 q0 q1 b

TCS : UNIT 1 35
 FSM WITH OUTPUT: MEALY MACHINE
Mealy machines are also finite state machines with output value and its output depends
on present state and current input symbol.
It can be defined as (Q, ∑, q0, δ, Δ, λ) where:

Q : set of all states.

Σ : set of input symbols. ( Symbols which machine takes as input )

q0 : Initial state. ( Starting state of a machine )

δ : Transition Function, defined as δ : Q X Σ --> Q

Δ: set of output symbols

λ : Output Function, defined as λ : Q X Σ --> Δ

TCS : UNIT 1 36
 Current Next State
State
Input = a Input = b
n n
State Output State Output

q0

q1
Input: abba

Current Next State

State
Input = a Input = b

State Output State Output

q0 q0 0 q1 1

q1 q1 1 q0 0

TCS : UNIT 1 37
 DIFFERENCE BETWEEN MOORE & MEALY MACHINE
MOORE MACHINE MEALY MACHINE
Output depends on the present state as w
Output depends only upon the present state.
present input.
If input string length is n o/p string leng
If input string length is n o/p string length will be n+1 be n only.

More states are required. Less number of states are required.

There is more hardware requirement for c
There is less hardware requirement for circuit implementation.
implementation.

Output Function: λ : Q --> Δ Output Function: λ : Q X Σ--> Δ

Synchronous output and state generation. Asynchronous output generation.
They react slower to inputs(One clock cycle later). They react faster to inputs.
Output is placed on states. Output is placed on transitions.
Easy to design. It is difficult to design.
TCS : UNIT 1 38
MOORE TO MEALY CONVERSION

Current Next State

State
Input = 0 Input = 1
State Output State Output
q0 q0 0 q1 1

q1 q2 0 q0 0
q2 q0 0 q1 1

TCS : UNIT 1 39
 MEALY TO MOORE CONVERSION

Mealy : m state and n output symbol

Moore: Maximum number of states = m X n

TCS : UNIT 1 40