We already described FA in the previous pages. There are 2 kinds of Finite Automaton, 1. DFA 2.NFA. Here introduced the concept of non-determinism and determinism.
Deterministic FA :- This is a FSM with a input string and a set of Accepting states (F). Formally a 5-tuple (Q,Σ,δ,q0,F) represents the Structure. Here machine read the symbol , progress head one step right and take a deterministic jump [ A jump where from a current state one can go to a single next state ] from current state to new state with respect to the read symbol.
Non-Deterministic FA :- This is a non-deterministic FSM [ Normally FSM are deterministic but we can also make it non-deterministic by allowing multiple possible next state from current state w.r.t single read symbol . Control would choose totally randomly one of the next state from those possible next states, as it could only be in only one state at a time ].
Practically then for each symbol and each current state there will be multiple possible next state and so in a obvious consequence there could be multiple path of control flow and we don't know which path the control will go. But now we can say that the NFA will accept some string if ∃ at least one path ending in a accepting state.
So, formally NFA will also be a 5-tuple same as DFA, only difference is δ: Q × Σ → 2Q
With δ we sometime want to see the transition function for a string and we call it δ'.
It is designed as -
1. ∀ (s,a) ∈ ( ( Σ*- ε ), Σ ) → δ'(s.a) = δ'(s).δ(a)
2. δ'(ε) = φ
Deterministic FA :- This is a FSM with a input string and a set of Accepting states (F). Formally a 5-tuple (Q,Σ,δ,q0,F) represents the Structure. Here machine read the symbol , progress head one step right and take a deterministic jump [ A jump where from a current state one can go to a single next state ] from current state to new state with respect to the read symbol.
Non-Deterministic FA :- This is a non-deterministic FSM [ Normally FSM are deterministic but we can also make it non-deterministic by allowing multiple possible next state from current state w.r.t single read symbol . Control would choose totally randomly one of the next state from those possible next states, as it could only be in only one state at a time ].
Practically then for each symbol and each current state there will be multiple possible next state and so in a obvious consequence there could be multiple path of control flow and we don't know which path the control will go. But now we can say that the NFA will accept some string if ∃ at least one path ending in a accepting state.
So, formally NFA will also be a 5-tuple same as DFA, only difference is δ: Q × Σ → 2Q
With δ we sometime want to see the transition function for a string and we call it δ'.
It is designed as -
1. ∀ (s,a) ∈ ( ( Σ*- ε ), Σ ) → δ'(s.a) = δ'(s).δ(a)
2. δ'(ε) = φ
No comments:
Post a Comment