Finite automata and regular expressions

Finite automata and regular expressions describe exactly the same family of languages: this is one of the founding results of theoretical computer science (Kleene's theorem). Concretely, for every deterministic finite automaton, there exists a regular expression that recognizes exactly the same set of words, and conversely.

Let's take our example again: the automaton that accepts words ending in «ab» over the alphabet {a, b}. The equivalent regular expression is written:

Automaton (words ending in «ab»)          <-->     Equivalent regular expression

  --> (q0) --a--> (q1) --b--> (( q2 ))                     (a|b)*ab
        ^ loop «b»   ^ loop «a»
        |______________|

  (a|b)*   = any prefix made of «a» and «b»   (corresponds to the q0/q1 loop)
  ab       = must end with «a» then «b»       (corresponds to the final path to q2)

This expression reads: "any sequence of a's and b's (possibly empty), necessarily followed by a then b". The part «(a|b)*» corresponds exactly to the loop between q0 and q1 that absorbs any prefix, and the final «ab» corresponds to the path q0 -> q1 -> q2 that triggers acceptance.

This equivalence is not just a theoretical curiosity: it is the basis of pattern-matching engines (grep, form validators, compiler lexical analyzers). When you write a regular expression in a programming language, it is generally compiled into a finite automaton before being run on the text, precisely because an automaton runs in linear time, letter by letter, never backtracking.

Classic pitfall: believing that every "modern" regular expression (with lookaheads, backtracking...) corresponds to a simple finite automaton. True theoretical regular expressions (those of Kleene's theorem) are more restricted than the extended "regex" of certain programming languages, which add features going beyond classic finite automata.