NON-DETERMINISTIC FINITE AUTOMATA (NFA)

A Non-Deterministic Finite Automata is defined as a five tuple notation as like DFA:

N=(Q,𝜮,𝜹,q0,F)

where Q is set of finite number of states
𝜮 is an input alphabet
𝜹 be the transition function which can be defined as 𝜹:QX𝜮->2^Q Here QX𝜮 represents the Cartesian product of the sets Q & 𝜮 and 2^Q is the power set of Q
q₀ be the starting state.
F be the set of final states.

The main difference between NFA and DFA is

1. For every input alphabet there is only one transition in DFA and in NFA more than one transition is acceptable for every input alphabet.

2. In DFA transition is must for every input alphabet whereas in NFA user may or may not give the transition to each input alphabet.

3. In DFA only one path is used to say whether the string is accepted or rejected where as in NFA number of paths  occur and if all the paths die the string is rejected otherwise any one of the paths gives the accepted path.

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.