DFA & NFA

In the course "Formal Language", we learned about "DFA and NFA", and here's my study notes.

Reference

1. http://stackoverflow.com/questions/3978438/dfa-vs-nfa-engines-what-is-the-difference-in-their-capabilities-and-limitations
2. DFA http://en.wikipedia.org/wiki/Deterministic_finite_automaton
3. NFA http://en.wikipedia.org/wiki/Nondeterministic_finite_automaton

Definitions

Finite Automaton

A finite automaton is a processor that has states and reads input, each input character potentially setting it into another state.

 In my opinion, we can see this as a finite state machine.

Deterministic Finite Automaton (1943)

A finite state machine that accepts/rejects finite strings of symbols and only produces a unique computation (or run) of the automaton for each input string. 'Deterministic' refers to the uniqueness of the computation.

In one state at a time.

Nondeterministic Finite Automaton (1959)

A finite state machine that (1)does not require input symbols for state transitions and (2)is capable of transitioning to zero or two or more states for a given start state and input symbol.

In more than one state at a time.

Difference between DFA and NFA

• all transitions are uniquely determined
• an input symbol is required for all state transitions
• DFAs are easier to understand, but NFAs are generally smaller.