Discrete Mathematics/Finite state automata

From Wikibooks, open books for an open world
< Discrete Mathematics
Jump to: navigation, search

Formally, a Deterministc Finite Automaton (DFA) is a 5-tuple where:

  • Q is the set of all states.
  • is the alphabet being considered.
  • is the set of transitions, including exactly one transition per element of the alphabet per state.
  • is the single starting state.
  • F is the set of all accepting states.

For a DFA, can be viewed as a function from .

Example: Consider the DFA with transitions given by table:

a b
p q p
q p q

It is easy to verify that this DFA accepts the input "aaa".

Similarly, the formal definition of a Nondeterministic Finite Automaton is a 5-tuple where:

  • Q is the set of all states.
  • is the alphabet being considered.
  • is the set of transitions, with transitions and any number of transitions for any particular input on every state.
  • is the single starting state.
  • F is the set of all accepting states.

For a NFA, can be viewed as a function from where is the power set of .

Note that for both a NFA and a DFA, is not a set of states. Rather, it is a single state, as neither can begin at more than one state. However, a NFA can achieve similar function by adding a new starting state and epsilon-transitioning to all desired starting states.

The difference between a DFA and an NFA being the delta-transitions are allowed to contain epsilon-jumps(transitions on no input), unions of transitions on the same input, and no transition for any elements in the alphabet.

For any NFA , there exists a DFA such that