## Introduction

A **deterministic finite automaton (DFA)** is a finite-state machine that accepts or rejects a given string of symbols by running through a state sequence that is uniquely determined by the string in the theory of computation.

For each input symbol, the state to which the machine will move can be determined using DFA. It's called as a Deterministic Automaton as a result of this. As it contains a finite number of states, the machine is called a Deterministic Finite Machine or Deterministic Finite Automaton.

Read About - __Symbol Table Operations__

## Representation of DFA

It is represented as 5 tuples (Q, âˆ‘, Î´, q0, F) where:

- Q represents the finite states
- âˆ‘ represents the is a finite set of symbols, also called the alphabet
- Î´ represents the transition function where Î´: Q Ã— âˆ‘ â†’ Q
- q0 represents the initial state from where any input is processed
- F represents the set of final state of Q.

**Example:**

The following is an example of a DFA M with a binary alphabet that accepts an even number of 0s in the input.

M = (Q, Î£, Î´, q_{0}, F) where

- Q = {S
_{1}, S_{2}} - q
_{0}= S_{1} - Î£ = {0, 1}
- F = {S
_{1}}

Î´ is represented by the following table

From | Next State from input 0 | Next State from input 1 |
---|---|---|

s1 | s2 | s1 |

s2 | s1 | s2 |

A DFA is a state machine built up of states and transitions that can accept or reject a finite string made up of a series of symbols and evaluate it to a predefined language across a predefined set of characters. We represent states with circles and transitions with directed arrows. Every state must have each symbol radiating from it, or it will not be characterized as a DFA. The machine is known as a Deterministic Finite Machine since it has a finite number of states.

Let us take an example to understand it in a better way:

Consider a machine that accepts strings containing at least one a from the alphabets a and b.

In the above picture, the initial state of the machine is q0, and the final state of the machine is qf, the state which determines whether the string is accepted or not.

Assume we have the string 'ba.'

The letter 'b' is the first to enter the system.

As it can be seen in the diagram above when b enters the system, it is accepted by q0 and remains there. When we give the machine the symbol a, we can see that when q0 accepts a, it proceeds to the final state, qf. (The double circles represent the final state.)

The string a is accepted by the machine and the string has ended, we can conclude that the given string is accepted by the DFA.

Also read - Arden's theorem