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𝜮->2Q Here QX𝜮 represents the Cartesian product of the sets Q & 𝜮 and 2Q is the power set of Q
q0 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.
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𝜮->2Q Here QX𝜮 represents the Cartesian product of the sets Q & 𝜮 and 2Q is the power set of Q
q0 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.
No comments:
Post a Comment