# Deterministic Finite Automata

The term **Deterministic** means the uniqueness of the computation. It is a finite state machine that either accepts or rejects strings of symbols, and for each input string it returns a unique computation. It has a set of states and rules for going from one state to another, depending on the input symbol. When the machine is in a given state and reads the next input symbol, we know what the next state will be - it is determined. It reads only one input symbol at a time from the tape, and after that it decides whether to accept or reject the input.

A **DFA** is defined as an abstract mathematical concept, but is often implemented in hardware and software for solving different specific problems such as lexical analysis and pattern matching.

## Parts of DFA

A deterministic finite automata has three parts-

- A
**tape**to hold the input string. - A
**tape head**to read the input symbols. - A
**control**that contains three main parts – set of start states, set of transition functions and final states.

## Formal Definition of DFA

A **DFA** is five tuple, consisting of

##### (Q, ∑, δ, q0, F)

**Q**- A finite set of states.

**∑**- Alphabet of input symbols.

**δ**- A transition function that takes as argument a state and a symbol and returns a state.

### Q×Σ→Q

**q0**- A start state.

**F**- A set of final or accept states.

## Represent DFA with Transition Table

Here is an example of DFA using a transition table and a graph. The **→** indicates the start state and the ***** indicates the final state.

0 |
1 |
|||||

→q0 |
q1 | q0 | ||||

q1 |
q1 | q2 | ||||

*q2 |
q2 | q2 |

### DFA transition diagram of above transition table.

The formal **DFA** of the above example is -

##### Q={q0, q1, q2}

Σ ={0,1}

q0(start state) = q0

δ:Q×Σ→Q

F(final state) = {q2}

## Language accepted by DFA

The language **L(M)**, accepted and recognized by a DFA is the set of all strings **w** accepted by **M** -

##### L(M) = {w ∈ Σ^{*} | M accepts w}

Finite Automata

Non Deterministic Finite Automata