Finite Automata

Deterministic Finite Automata

A DFA can be described as a 5-tuple where

  • is the set of all states
  • is the alphabet. Which means the set of all input symbols
  • which is the state transition function is defined as
  • is the initial state
  • is the set of all final states
    A single state must have the same number of transitions as the number of elements in .

Non-deterministic Finite Automata

An NFA can be described as a 5-tuple where

  • is the set of all states
  • is the alphabet. Which means the set of all input symbols
  • which is the state transition function is defined as
  • is the initial state
  • is the set of all final states
    An NFA is not restrictive like a DFA and is not very strictly defined. It is therefore easier to work with and is often built up and converted to a DFA later.

Conversion to DFA

Subset construction

The algorithm is fairly simple

states = {unmarked q0}
while unmarked state T in states:
	mark T
	for each input symbol a:
		U = eClosure(transition(T, a))
		if U not in states: add(unmarked U)
		transition_table[T, a] = U
	end
end