1.the transition function for nfa ie delta is multi valued where as for dfa it is single valued. 2.checking membership is easy with dfa where it is difficult for nfa
3.construction of nfa is very easy where for dfa it is difficult
4.space required for dfa is more where for nfa it is less.
5. In the state diagram of DFA, for every symbol of the alphabet, we specify its
5. In the state diagram of DFA, for every symbol of the alphabet, we specify its
one and only one state transition. But for NFA, we do not need to specify how
does the NFA react according to some symbol. In the case that the behavior of the NFA is not
specified when read some symbol, we say the NFA (or a branch of NFA) dies. NFA can specify multiple states that a state can transit to when read a symbol. (DFA can and an only can specify one next state)
6. NFA can use the symbol e, DFA can not. e means that NFA can generate a new branch without reading any input symbol
7. NFA can be understood as some machine that can reproduce itself. Or there will be multiple little machines computing at the same time, listening to the next symbol at the same time.
8. NFA will not reject the input string if one of its branch dies or reject the string. But if all of the branches of NFA die or reject the string, we say the NFA reject the string. As long as one branch of the NFA accept the string, we say that the NFA accept the string.
DFA Vs. NFA
(1)
· For Every symbol of the alphabet, there is only one state transition in DFA.
· We do not need to specify how does the NFA react according to some symbol.
(2)
· DFA can not use Empty String transition.
· NFA can use Empty String transition.
(3)
· DFA can be understood as one machine.
· NFA can be understood as multiple little machines computing at the same time.
•When processing a string in a DFA, there is
always a unique state to go next when each
character is read
•It is because for each state in DFA, there is
exactly one state that corresponds to each
character being read
•In an NFA, several choice (or no choice) may
exist for the next state
•Can move to more than 1 states, or nowhere
•Can move to a state without reading anything
The only difference between a DFA (deterministic finite automaton) and a NFA (nondeterministic finite automaton) is found in the transition function.
A NFA's transition function is less restrictive than a DFA's because it allows you to have several transitions from a given state to zero, one or more states for the *same input symbol*. On the other hand, a DFA specifies exactly one state that may be entered for a given state and input symbol combination.
For example, let's say you are in state 0, then in a NFA you can have all these transitions upon reading input symbol 'a':
0 -> 1
0 -> 2
0 -> 0
You see that you have several choices as to which state you can enter from state 0 for the same input symbol 'a'.
Contrast this to a DFA where you should have exactly one transition going from state 0 upon reading input symbol 'a' (for example 0 -> 2). The DFA is so called "deterministic" because it has one and only one transition for every possible input symbol at every state.
IMPORTANT:
You should understand that even though a NFA may seem more powerful because it is less restrictive, this is not the case at all. It has been proven that both are equivalent and that a NFA can *always* be reduced to a DFA. The real advantage then of a NFA is that it is sometimes easier, or more natural, to build a NFA than a DFA for some problems (this NFA can thereafter be reduced to a DFA using some algorithm).
A NFA's transition function is less restrictive than a DFA's because it allows you to have several transitions from a given state to zero, one or more states for the *same input symbol*. On the other hand, a DFA specifies exactly one state that may be entered for a given state and input symbol combination.
For example, let's say you are in state 0, then in a NFA you can have all these transitions upon reading input symbol 'a':
0 -> 1
0 -> 2
0 -> 0
You see that you have several choices as to which state you can enter from state 0 for the same input symbol 'a'.
Contrast this to a DFA where you should have exactly one transition going from state 0 upon reading input symbol 'a' (for example 0 -> 2). The DFA is so called "deterministic" because it has one and only one transition for every possible input symbol at every state.
IMPORTANT:
You should understand that even though a NFA may seem more powerful because it is less restrictive, this is not the case at all. It has been proven that both are equivalent and that a NFA can *always* be reduced to a DFA. The real advantage then of a NFA is that it is sometimes easier, or more natural, to build a NFA than a DFA for some problems (this NFA can thereafter be reduced to a DFA using some algorithm).
The relationship between DFA and NFA
* DFA is a kind of NFA. But the reverse is not true.
* DFA and NFA have the same capability. Every language that can be recognized
by a DFA can also be recognized by a NFA. The reverse is also true.
* Although they have the same power, usually it will be more easy to design NFA,
since we have more flexible way to describe NFA.
* Both DFA and NFA can only has one start state. They can have multiple accept
state.
Walang komento:
Mag-post ng isang Komento