Deterministic Finite Automata(DFA)

A Deterministic Finite Automata(DFA) is a five tuple notation can be represented as
D=(Q,𝚺,𝛿,q₀,F).
Where  D is the name of the DFA.
Q is the finite set of states.
𝚺 is the set of input alphabet.
𝛿 is the transition function which can be mapped from Qx𝚺->Q.
q₀ is the starting state of the machine.
F is the finite set of final states Which is an acceptance state of the machine .


Example:
Design DFA which accepts the string 1100 only.
Solution
Let the DFA D=(Q,𝚺,𝛿,q₀,F).

Where Q={q0,q1,q2,q3,q4,q5}

 𝚺 be the input alphabet which contains the symbols 0 and 1 i.e.,{0,1}.
q0 be the starting sate
F be the final state which is an acceptance state i.e., according to our machine it is q4. It is represented as a double circle in transition diagram.

 

The Transition table for the above DFA is as follows 

𝛿	0	1
q0 (start state)	q5	q1
q1	q5	q2
q2	q3	q5
q3	q4	q5
q4(final state)	q5	q5
q5	q5	q5

Acceptance of a string

Let w=1100

𝛿(q0,1100)---> q0 upon 1 transition the machine enter into q1 state which gives the result as
                         𝛿(q1,100).
                 ----> Now again, q1 upon 1 transition the machine enters into q2 state which gives the result as
                         𝛿(q2,00)
               Similarly,
                ----->𝛿(q3,0)
               ------>q4 which belongs to final state 
So, the given  string 1100 is accepted by the given DFA.


Not Acceptance of a string
Let choose the string other than 1100
i.e., Let w=1001

𝛿(q0,1001)---->𝛿(q1,001)
                 ----->𝛿(q5,01)
                 ----->𝛿(q5,1)
                 ------>q5 which does not belongs to the set of final state.

So, the given string 1001 is not accepted by the given DFA.