0

11kviews

Distinguish between DFA and NFA

written 8.4 years ago by teamques10 ★ 68k

modified 2.8 years ago by pedsangini276 • 4.8k

Mumbai university > Comp > SEM 4 > TCS

Marks: 5M

Year: May 2015

theory of computation

ADD COMMENT FOLLOW SHARE EDIT

1 Answer

0

210views

written 8.4 years ago by teamques10 ★ 68k

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:

ADD COMMENT SHARE EDIT