Finite Automata (FA) is an abstract mathematical model used in Theory of Computation (TOC) to recognize patterns in input strings. It is one of the simplest computational models and forms the foundation for understanding Regular Languages. A Finite Automaton processes an input string one symbol at a time and determines whether the string belongs to a particular language.

A Finite Automaton consists of a finite number of States, Transitions, and Input Symbols. It starts from an initial state, processes each input symbol sequentially, and moves from one state to another according to predefined transition rules.

After processing the complete input string, if the automaton reaches an Accepting (Final) State, the input string is accepted. Otherwise, the string is rejected.

There are two main types of Finite Automata: Deterministic Finite Automata (DFA) and Non-deterministic Finite Automata (NFA). Although they work differently, both can recognize exactly the same set of Regular Languages.

Finite Automata are widely used in Compiler Design, Lexical Analysis, Pattern Matching, Text Processing, Network Protocols, Digital Circuit Design, and many other computer science applications.

Features of Finite Automata

1. Input

The Input is a sequence of symbols or characters taken from an Alphabet (Σ). The automaton reads one symbol at a time until the entire string has been processed.

Example

If Σ = {0,1}, then possible input strings are:
1010
111
00101

2. Output

After processing the input string, the automaton produces one of two outputs:

• Accept – The input belongs to the language.
• Reject – The input does not belong to the language.

3. States of Automata

A State represents the current condition or configuration of the automaton while processing an input string. Every Finite Automaton contains one Start State, one or more intermediate states, and one or more Accepting (Final) States.

Example

States = {q0, q1, q2}
Start State = q0
Final State = q2

4. State Transition

A State Transition defines how the automaton moves from one state to another when an input symbol is read. These transitions are determined by the Transition Function.

Example

Current State = q0
Input = a
Next State = q1

5. Output Relation

The final decision depends on the state where the automaton stops after reading the entire input string.

If the final state is an Accepting State, the string is accepted.
If the final state is not an accepting state, the string is rejected.

Working Example

Suppose a Finite Automaton accepts all strings ending with 1 over the alphabet Σ = {0,1}.

Accepted Strings:
1
01
101
111

Rejected Strings:
0
10
1100

The automaton accepts a string only if the last symbol is 1.

A Finite Automaton (FA) is formally defined as a mathematical model consisting of five components. These components describe how the automaton processes input symbols, changes states, and determines whether an input string is accepted or rejected.

A Finite Automaton is represented by the 5-tuple:

FA = {Q, Σ, q₀, F, δ}

Each component of the tuple has a specific meaning and plays an important role in the operation of the automaton.

Components of Finite Automata

1. Q – Finite Set of States

Q represents the finite collection of states in the automaton. A state indicates the current condition of the machine while processing an input string.

Example

Q = {q0, q1, q2}

Here, the automaton has three states: q0, q1, and q2.

2. Σ – Input Alphabet

Σ (Sigma) is the finite set of input symbols that the automaton can read. Every input string must be formed using symbols from this alphabet.

Example

Σ = {0,1}
Σ = {a,b}

3. q₀ – Initial State

q₀ is the Start State from which the automaton begins processing every input string. There is only one initial state in a finite automaton.

Example

q₀ = q0

4. F – Set of Final States

F is the set of one or more Accepting (Final) States. If the automaton reaches any state in F after processing the entire input string, the string is accepted.

Example

F = {q2}
or
F = {q1, q3}

5. δ – Transition Function

The Transition Function (δ) defines how the automaton moves from one state to another after reading an input symbol.

Mathematically,

δ : Q × Σ → Q

Example

δ(q0, a) = q1
δ(q1, b) = q2

This means the automaton moves from q0 to q1 when it reads a, and from q1 to q2 when it reads b.

Summary of the 5-Tuple

Types of Finite Automata

There are two major types of Finite Automata.

1. Deterministic Finite Automata (DFA)

In a DFA, every state has exactly one transition for each input symbol. Therefore, for every input, the next state is uniquely determined.

Characteristics

• Only one possible next state for each input symbol.
• No ε-transition is allowed.
• Easy to implement and analyze.
• Recognizes all Regular Languages.

2. Non-Deterministic Finite Automata (NFA)

In an NFA, a state may have multiple possible transitions for the same input symbol, or even an ε-transition. The automaton accepts the string if at least one possible path reaches an accepting state.

Characteristics

• Multiple transitions for the same input are allowed.
• ε-transition may exist.
• More flexible than DFA.
• Every NFA can be converted into an equivalent DFA.

A Deterministic Finite Automata (DFA) is a type of Finite Automata (FA) in which, for every state and every input symbol, there is exactly one possible next state. Since the next state is uniquely determined, the automaton behaves in a deterministic manner. DFA is widely used for recognizing Regular Languages.

A DFA does not allow ε (Null) Transitions. Therefore, every state must have a defined transition for each input symbol in the alphabet.

Formal Definition of DFA

A DFA is represented by the following 5-tuple:

DFA = {Q, Σ, q₀, F, δ}

Each component has a specific meaning in the operation of the automaton.

Components of DFA

1. Q – Finite Set of States

Q is the finite collection of all states in the automaton.

Example

Q = {q0, q1, q2}

2. Σ – Input Alphabet

Σ (Sigma) is the finite set of input symbols accepted by the automaton.

Example

Σ = {0,1}
Σ = {a,b}

3. q₀ – Initial State

q₀ is the starting state from which the DFA begins processing every input string.

Example

q₀ = q0

4. F – Set of Final States

F is the set of one or more Accepting (Final) States. If the DFA stops in any of these states after reading the complete input, the string is accepted.

Example

F = {q2}

5. δ – Transition Function

The Transition Function (δ) defines how the DFA moves from one state to another for every input symbol.

Mathematically,

δ : Q × Σ → Q

This means that for every combination of a state and an input symbol, there is exactly one next state.

Example

δ(q0, a) = q1
δ(q0, b) = q2

If the current state is q0 and the input symbol is a, the DFA always moves to q1. There is no alternative path.

Characteristics of DFA

• Every state has exactly one transition for each input symbol.
• ε (Null) Transition is not allowed.
• Only one possible computation path exists for every input string.
• The next state is always uniquely determined.
• DFA recognizes all Regular Languages.

Example

Suppose Σ = {0,1}. A DFA accepts all binary strings ending with 1.

Accepted Strings:
1
01
101
1111

Rejected Strings:
0
10
1000

The DFA accepts a string only when the last input symbol is 1.

Advantages of DFA

• Easy to implement and understand.
• Faster string recognition because only one path is followed.
• Commonly used in Lexical Analysis, Compiler Design, Pattern Matching, and Text Processing.

A Non-Deterministic Finite Automata (NFA) is a type of Finite Automata (FA) in which a state may have one, multiple, or no transitions for the same input symbol. Unlike a Deterministic Finite Automata (DFA), an NFA can have more than one possible path while processing an input string.

Another important feature of an NFA is the use of ε (Epsilon or Null) Transition. An ε-transition allows the automaton to move from one state to another without reading any input symbol.

Although an NFA may have multiple computation paths, an input string is accepted if at least one path ends in an Accepting (Final) State.

Formal Definition of NFA

An NFA is represented by the following 5-tuple:

NFA = {Q, Σ, q₀, F, δ}

The components of an NFA are the same as those of a DFA, but the transition function is different.

Components of NFA

Q – Finite set of states.
Σ – Finite set of input symbols.
q₀ – Initial (Start) State.
F – Set of Accepting (Final) States.
δ – Transition Function.

The transition function of an NFA is defined as:

δ : Q × (Σ ∪ {ε}) → 2^Q

This means that for a given state and input symbol, the NFA may move to zero, one, or multiple next states. It may also move using an ε-transition without consuming any input.

Characteristics of NFA

• A state may have multiple transitions for the same input symbol.
• ε (Null) Transition is allowed.
• Multiple computation paths may exist for a single input string.
• A string is accepted if at least one path reaches an Accepting State.
• Every NFA has an equivalent DFA.

Example

Construct an NFA that accepts all strings ending with a.

Given:

Σ = {a, b}
Q = {q0, q1}
Start State = q0
Final State = {q1}

Transition Table

Here,
→ indicates the Start State.
* indicates the Accepting (Final) State.

Working Example

Input String = "bba"

q0 --b→ q0
q0 --b→ q0
q0 --a→ {q0, q1}

Since one possible path reaches the final state q1, the string "bba" is accepted.

Input String = "abb"

The last symbol is b, so no computation path ends in q1. Therefore, the string is rejected.

The major differences between DFA and NFA are given below.