Deterministic Finite Automaton (DFA)

Deterministic Finite Automaton (DFA) is the simplest version of Finite Automaton and is used to accept Regular Languages in Theory of Computation. This is one of the most useful theoretical computation model.

Table of contents:

Deterministic Finite Automaton (DFA)
Properties of DFA
Examples of DFA
DFA Membership Problem
How to prove a Language is not Regular? (using DFA)
Minimization algorithm for DFA
Deterministic Finite Automata (DFA) vs Nondeterministic Finite Automata (NFA)

Prequisite: Regular Language, Regular Grammar, Finite Automaton

Let us get started with Deterministic Finite Automaton (DFA).

Deterministic Finite Automaton (DFA)

Deterministic Finite Automaton (DFA) in Theory of Computation is the simplest version of Finite Automaton which is used to model Regular Languages.

Definition of DFA:

DFA is denoted as a 5 tuple: M = (Q, Σ, δ, q₀, F) where:

Q is a finite set of states
Σ is the finite set of alphabet
δ is the transition function and consists of transitions like Q x Σ -> Q
q₀ belongs to Q and it is the start state
F is a super subset of Q and is the set of accept states.

Other useful definitions related to DFA:

L(M) is the language accepted by a given DFA M.
Let w be a string in Σ*: w = a₁a₂...a_N. M accepts w if there is a sequence of states which starts at q₀ and ends at an accept state by processing all characters in w.
A language L is known as DFA Recognizable if there exists a DFA M such that L = L(M).

DFA has resulted in the discovery of Knuth Morris Pratt Algorithm in 1976 which is a very popular string searching algorithm today.

Examples of DFA

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

Q = {q₀, q₁, q₂, q₃}
Σ = {0, 1} q₀ is the start state
F = {q₁, q₂} is the set of accept states
δ is the transition function and is denoted for the following table:

δ	Input: 0	Input: 1
q₀	q₀	q₁
q₁	q₂	q₂
q₂	q₃	q₂
q₃	q₀	q₂

The above table is known as "State Transition Table".

Following is the state diagram of our DFA:

deterministic-finite-automaton

Note:

Double circle denotes accept states.
Single circle denotes a transition state.

Properties of DFA

Properties of DFA are:

If a Language L is a Regular Language, then there must be a Deterministic Finite Automaton M such that L(M) = L.
If Language L is a Regular Language, then the Language ~L (complement of L) is also a Regular Language. So, if there is a Deterministic Finite Automaton M for L, there exists another Deterministic Finite Automaton N for ~L.
A model of Computation is called Deterministic if there is only one choice at every step for a given input. It can be modeled using Deterministic Finite Automaton (DFA).
Deterministic Finite Automaton is always complete that is transition from every state has been defined for every possible input.
DFA is closed under the following operation:
- Union
- Intersection
- Concatenation
- Negation
- Kleene closure
- Reversal
- Quotient
- Substitution
- Homomorphism

This summarize the properties of Deterministic Finite Automaton.

DFA Membership Problem

DFA Membership Problem is the problem to determine if a given word belongs to a Language L which is generated using DFA M.

Let DFA M = () and w = w₁ ... w_m

Algorithm for DFA Membership:

p = q₀
for i = 1 to m, do p = (p, w_i)
If p belongs to F, then return YES else return NO.

DFA Membership Problem can be solved in Linear Time O(N).

There are other similar problems which can be solved using a DFA:

Emptiness Problem: Does a DFA accept any string?
Universality problem: Does a DFA accept all strings?
Equality Problem: Does two DFAs recognize the same language
Inclusion Problem: Does the language recognized by one DFA included in language recognized by another DFA.
Minimization Problem: Does a DFA have the minimum number of state for a given language?

As there are algorithms to solve all these problems in linear time O(N) for DFA, this makes DFA is very useful model in Theory of Computation.

How to prove a Language is not Regular?

Steps to prove a Language is not Regular (using DFA):

Let the given language be L.
Assume there exists a DFA M for which L(M) = L.
Use Pigeonhole principle to show that there exists two distinct strings x and y which will reach the same state in M.
Show that there exists a string z such that xz belongs to L but yz does not belong to L.
This results in a contradiction as M should accept either both or none.

Therefore, in these lines, you can prove that the given Language L is not Regular Language using DFA.

Minimization algorithm for DFA

Two core definitions:

DFA A is equivalent to DFA B if L(A) = L(B)
DFA A is minimal if there is no DFA B equivalent to A which has less number of states than A.

There exists an algorithm to minimize the number of states in a given DFA.

The steps of Minimization algorithm for DFA are as follows:

Remove all states that cannot be reached from the stating state of DFA A.
Make a 2D table where rows and columns are denoted by different states of DFA A.
Initialize table with X for the cells (i, j) which involve one of the states i or j as accept state.
Mark a cell (a, b) with X if (a, b) does not have a mark and there exists a transition from cell (a, c) and (b, c) and one of them has the mark. Do this for all cells.
For every state i, define a list of cells which are not marked.
Construct a new DFA with minimal states by declaring each cell in the above list to be a state. Initial state be the first row state.Create the transitions from the table.

Deterministic Finite Automata (DFA) vs Non-deterministic Finite Automata (NFA)

Deterministic Finite Automata (DFA) is equivalent to Nondeterministic Finite Automata (NFA). For proving that for every NFA, there is an equivalent DFA in 1959, the Turing Award was given to Rabin and Scott.

The major difference between DFA and NFA is:

DFA has only one transition from a given state for a given input. NFA can have multiple transitions from a given state for a given input.

Deterministic Finite Automaton	None-Deterministic Finite Automaton
Difficult to construct	Easy to construct
Usually larger than DFA	Exponentially smaller
Algorithms are complex usually	Algorithms are simple
Fast acceptance test	Slow acceptance test

This makes NFA Non-deterministic as there is not a deterministic path that is a single option / path.

With this article at OpenGenus, you must have a strong idea of Deterministic Finite Automata (DFA) in Theory of Computation.