written 7.8 years ago by
teamques10
★ 64k
|
modified 2.2 years ago
by
pedsangini276
• 4.7k
|
Mumbai university > Comp > SEM 4 > TCS
Marks: 5M
Year: May 2015
|
written 7.8 years ago by
teamques10
★ 64k
|
| DFA | NFA |
|---|---|
| DFA(Deterministic Finite Automata) is the one which has a distinguished state transition for every input that it encounters | NFA(Non-Deterministic Finite Automata) is the one which has either more than one or no state transitions at all for an input that it encounters |
| DFA’s do not have ε transitions | NFA’s have ε transitions |
| DFA’s do not have contradictory transitions | NFA’s can have contradictory transitions |
| As every DFA is an NFA, DFA’s do not need to be specifically converted to equivalent NFA’s. | NFA’s can be converted to equivalent DFA’s using ε -closure |
| DFA’s are relatively more difficult to construct than NFA’s | NFA’s are easier to construct |
Examples:
and 4 others joined a min ago.