# 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_{0}, 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
_{0}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
_{1}a_{2}...a_{N}. M accepts w if there is a sequence of states which starts at q_{0}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_{0}, F) where:

Q = {q_{0}, q_{1}, q_{2}, q_{3}}

Î£ = {0, 1} q_{0} is the start state

F = {q_{1}, q_{2}} is the set of accept states

Î´ is the transition function and is denoted for the following table:

Î´ | Input: 0 | Input: 1 |
---|---|---|

q_{0} |
q_{0} |
q_{1} |

q_{1} |
q_{2} |
q_{2} |

q_{2} |
q_{3} |
q_{2} |

q_{3} |
q_{0} |
q_{2} |

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

Following is the state diagram of our DFA:

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_{1} ... w_{m}

Algorithm for DFA Membership:

- p = q
_{0} - 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.