Overview of Finite Automata

1/May/2016by Valkryst, Updated 29/June/2017

A finite automaton, also known as a finite state machine, is an imaginary machine which takes input, reads that input step-by-step, and either accepts or rejects the input.

There are two types of finite automata, DFAs (Deterministic Finite Automata) and NFAs (Non-deterministic Finite Automata).

Basic Information:

A finite automaton is a combination of five different parts.

  1. Q = The finite set of states of the automaton.
  2. Σ = The alphabet accepted by the automaton.
  3. δ = The transition function.
  4. q0 = The starting state.
  5. F = The set of accept states.

The Alphabet:

The alphabet of an automaton is a set of characters that the automaton recognizes.

An alphabet can be {0, 1}, which allows the automaton to work with ones and zeroes, or {a, b, c} which allows it to work with 'a's 'b's and 'c's. The characters could even be entire words such as {one, two, three}.

There is one special character that can be used. It is the null or empty character, ε.

The Input String:

A finite automaton can process any input created using the alphabet.

For example, let's say our alphabet is {0, 1}. We would be able to process the strings "0", "1", "00", "01", "10", "11", "100", etc...

If our alphabet was {a, b, c, d, e}, then we could process "a", "b", "c", "d", "e", "abcde", "adec", etc...

Say we alter the previous alphabet to accept the "empty" character {a, b, c, d, e, ε}. We would then be able to process "", "a", "b", "c", "e", etc... Notice how the first string is actually nothing.

The length of the string doesn't matter, the order of characters doesn't matter, but what does matter is that the string contains only characters of the alphabet.

The Language:

The language of a finite automaton is the set of all strings that, after being processed, are accepted by the automaton.

Anything that is rejected by the automaton, or cannot be processed by it, is not in the language of the automaton.

Deterministic Finite Automata:

All DFA diagrams will look similar to the image below. They begin at a starting state (red), transition to other states as input is read, and eventually end up on an accept (green) or reject state. The DFA below will accept both the strings "01" and "11".

When drawing a DFA, you should remember the following:

How A Transition Works:

Say, for example, a user inputs the string "0101" to the finite automaton in the image above.

As a secondary example, a user inputs the string "100" to the finite automaton.

As a final example, a user inputs the string "01" to the finite automaton.

Non-deterministic Finite Automata:

The first thing to note about NFAs is that all DFAs are NFAs, but not all NFAs are DFAs.

All NFA diagrams will look similar to the image of an DFA from the previous section. The key differences between NFAs and DFAs are as follows: