Finite Automata||DFA and NFA

 

Finite Automata:-

First mathematical abstract model of computing device is finite automata. Finite automata have five component just like computer.

Finite tape(auxiliary memory)read only divided into cell.Finite memory is read only not capable of writing. That is the main limitation of FA.That is used for recognize purpose only not computing(because not writing capability).FA is used in lexical analyzers for compiler.

In tape leftmost and rightmost symbol indicate Start and ending of the tape.Finite control move left to right and scan the symbol of the tape.

Limitation of Finite automata

• Finite automata used for recognizing purpose only not computing purpose.
• FA has head move left to right only not right to left and cannot write. So FA cannot remember its previous read symbol so it cannot used for computation because in computation knowledge of previous symbol is necessary.

Finite automata without output divided into two parts.

• DFA(Deterministic finite automata).
• NFA(Nondeterministic finite automata).

DFA

Deterministic finite automata that is used for recognizing purpose. DFA has 5 tuple(Q,∑,δ,q0,F).

• First tuple state that is set of state in DFA.
• Second tuple set of input in DFA.
• Third tuple transition function on (Q,∑)-> (Q) that is transition function.
• Fourth tuple is starting state of DFA.
• Fifth tuple is  accepting state in DFA.

NFA

NonDeterministic finite automata that is used for recognizing purpose and is easy to design as compare to dfa.More that one outgoing state possible on input. Nfa has 5 tuple(Q,∑,δ,q0,F).

• First tuple state that is set of state in NFA.
• Second tuple set of input in NFA.
• Third tuple transition function on (Q,∑)-> (2Q)
• Fourth tuple is starting state of NFA.
• Fifth tuple is  accepting state in NFA.

The main difference between a DFA and  NFA is only in transition function.In DFA transition function map on at most one state and in NFA  transition function maps on at least  one state for an input.

The language recognized by FA are regular language and these language are described by regular expression.Regular expression means to represent sets of string in algebraic manner that describe language accepted by finite automata. 

FA WITH OUTPUT:

Enhanced finite automata with output capability used in circuit design is FA with output. that is used for flip flop design and other logic circuit design . FA with output has  six tuple (Q,∑,δ,q0,F,Δ)

• First tuple state that is set of state .
• Second tuple set of input .
• Third tuple transition function on (Q,∑)-> (Q)
• Fourth tuple is starting state .
• Fifth tuple is  accepting state.
• six tuple is output.