28-09-2013, 03:10 PM
Non Deterministic Finite automaton and Deterministic Finite Automaton
Deterministic Finite automaton.pptx (Size: 801.46 KB / Downloads: 19)
NONDETERMINISTIC FINITE AUTOMATON
When the machine is in a given state and reads the next input symbol, we know what the next state will be - this is a deterministic automaton.
In a NFA, several choices may exist for the next state at any point.
Nondeterminism is a generalisation of determinism, so every DFA is automatically a NFA.
Constructing the DFA
first we need to determine the states. N has 3 states {1,2,3}, so we construct D with eight states (2 to the power of k).
So we get the states for D as { E, {1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}.
The start state is E({1}), the set of states that are reachable from 1 by traveling along E arrows, plus 1 itself. Hence start state is {1,3}.
Accept states are those containing N's accept state = {{1},{1,2},{1,3},{1,2,3}}.