# Deterministic Finite Automata Explanation In Theory Of Computation

You all know what is Finite Automata now.

The process is divided into two types,

- Deterministic Finite Automata
- Non Deterministic Finite Automata

So in this post, we’ll know the basics of what a deterministic finite automata is,

This DFA (Deterministic Finite Automata) process is defined by 5 tuples,

(Q, Σ, δ, q, F)

Looks complex right?

That’s what I thought too, but it’s nothing but representation of some simple methods.

q – This is a representation for initial state of a finite automata. Which means all other process in FA originates from this state. It accepts the string given by you.

Σ – This is known as input. You can take 0 or 1 as input symbols in finite automata. It’s used to transition from one state to another state.

F – This symbol is easy to remember because it means final state of the finite automata. It’s opposite of q (Initial state) which means it’s where the finite automata ends.

Q – It’s the set of all states. (including q and F)

δ – It represents the transition function. In simple word, when you’re on a state and you see a input 0 or 1. δ is responsible for deciding which states to go next after getting that specific input. (Q X ∑ –> Q)

This was the basic introduction to DFA. But what makes DFA different than others is its deterministic nature. Which means when you take transition you can only use one input for one destination.

For example, if you used 0 then you can’t use it for another transition.

But you can use 1 for the other.

Let’s take one example of a language with length of 2.

So if the alphabets are {a, b}

then probably the language will be {aa, ab, ba, bb}

So we’ll check for two inputs ab and aab

As you know it’s simple and we already know a,b is valid string and aab is invalid string.

But how will it decide in deterministic finite automata?

Let’s start with our initial state q.

We’ll take initial state X

From X we’ll give an input a which will transition to next state Y.

From Y we’ll give an input b which will transition to state Z.

Now there are two transitions ( We don’t have any more inputs left ) and we needed a length of 2 in language. So this string is valid now.

Now let’s take our second example of aab.

We’ll take ‘a’ as input which will go from X to Y and in case of ‘a’ input it’ll go from Y to Z. But we have another input left which is ‘b’ there are no more states left ( as the representation contains only length of 2 strings ) so it’ll go to a dead configuration state. Represented as d.

If anything went to d then it’s an invalid string.

But what we have only one input ‘a’

This will stop at Y. But Y is not our final state. So the string will be invalid.

Well, what if the language is accepts strings with length more than or equal to 2.

Then if you take abc as input this won’t go to dead configuration after final state Z. Now matter how much input you give, this is gonna return to final state. So it’ll be a valid string.

But let’s say if the length required is less than 2. And the input length is 0. Then the initial state will automatically be final state.