State, transition, initial state, and accepting states

A finite automaton is a very simple abstract machine: it is always in one state among a finite number of possible states, and it changes state with each letter it reads in a word. It is a fundamental model of theoretical computer science: it is used to describe text patterns, network protocols, user interfaces, or even the internal workings of a compiler's lexical analyzer.

Four notions are enough to define everything:

• a set of states (the possible situations the machine can be in);
• transitions (rules of the form: from a given state, upon reading a given letter, go to another given state);
• an initial state (the single starting state, before even reading the slightest letter);
• one or more accepting states (particular states: if the automaton is in one of them right after reading the entire word, the word is accepted, otherwise it is rejected).

General notation for an automaton:

  --> (q)       initial state   (the incoming arrow comes from no other state)
      (q)       ordinary state
     ((q))      accepting state (double circle)

     (q0) --x--> (q1)     (from q0, upon reading letter x, go to q1)

An automaton is said to be deterministic (DFA) when, for each state and each letter of the alphabet, there is exactly one possible transition: the machine can never hesitate. This is the simplest case to run and understand - it is contrasted with nondeterministic automata (NFA), more flexible to build but which allow several choices at once for the same letter.

Classic pitfall: confusing "accepting state" with the idea that the automaton would necessarily stop and stay there. In reality, the automaton keeps reading letters even after passing through an accepting state; only the state reached AFTER THE LAST letter of the word counts for deciding acceptance.

Another pitfall: forgetting the initial state. Two automata with the same states and the same transitions, but different initial states, can recognize totally different languages.