Theory of Computation | DFA - Deterministic Finite Automata

Automata are decision making machines, which decides whether a string belongs to a language or not.

An automaton is called deterministic, when it shows a unique path for change of state on every input.

Automata with definite number of states are called finite automata.

A Deterministic finite automaton(DFA) has both qualities,ie. it is deterministic and has finite number of states

---

A binary number is even if its LSB(Least Significant Bit) is zero (eg: 110 = 6 is even). If LSB is one, it is odd (eg: 111 = 7 is odd).

So if we are constructing an DFA which accepts all odd binary numbers,

our deterministic finite machine will have two states odd and even.

set of of all states Q = {O, E}

O - Odd

E - Even

Our machine requires inputs, the elemental binary numbers, i.e 0 or 1

These are called input alphabets Σ = {0, 1}

When you feed this a DFA with a inputs from MSB(Most Significant Bit) to LSB of a binary, when the zero comes as input the state has to be even when one the input the state will be odd.

Here the odd state is called finial state, where After giving LSB of the input to the machine, if the state is odd, concludes that the binary belong to language of set all odd binary numbers.

Final states are represented with F = { O }

Here the initial state is q₀ = { E }.

And the state transition can be represent in terms of function δ : Q x Σ ➡ Q

DFA Deterministic Finite Automata(Q, \sigma, \delta, \q0, F):

The state transition function describes what should be the next state when a symbol input is given to a state.

So, a DFA has mainly the following parameters :

1. Set of all states(Q)
2. Input alphabets (Σ)
3. Set of all final states F
4. Initial state q₀
5. State transition function δ : Q x Σ ➡ Q

| Automata -Basics | Non-Deterministic Finite Automata(NFA) | Home |