Kleene’s theorem

Theorem 1 (Kleene).

A languagePlanetmathPlanetmath over an alphabet is regularPlanetmathPlanetmathPlanetmath iff it can be accepted by a finite automaton.

The best way to prove this theorem is to visualize a finite automaton as a directed graphMathworldPlanetmath (its state diagramMathworldPlanetmathPlanetmath). We prove sufficiency and necessity separately.

Lemma 1.

Every regular language can be accepted by a finite automaton.


This is done inductively. We begin with atomic languages, and work our way up. First, note that , {λ}, {a} where aΣ are accepted by the following finite automata respectively:

Next, suppose that L1 and L2 are regular languages, accepted by A1 and A2 respectively. Then

  • L1L2 is accepted by the finite automaton A1A2, the juxtaposition of automata A1 and A2;

  • L1* is accepted by the finite automaton A1*, the Kleene star of automaton (http://planetmath.org/KleeneStarOfAnAutomaton) A1; and

  • L1L2 is accepted by A1A2, the union (http://planetmath.org/UnionOfAutomata) of A1 and A2.

Since a regular language can only be built up this way, the proof is completePlanetmathPlanetmathPlanetmathPlanetmathPlanetmath. ∎

Lemma 2.

Every language accepted by a finite automaton is regular.

Note that, using a state diagram of a finite automaton A, a word accepted by A is the label of a path that begins from one of the starting nodes and ends in one of the final nodes. In the proof, we build a sequence of languages


such that L1 is regular, and each Li+1 is constructed from Li by one of the regular operationsMathworldPlanetmath (union, concatenationMathworldPlanetmath, and Kleene star), so that in the end, Ln is also regular. Finally, we show that L(A) is a finite union of such L(n)’s, and therefore L(A) is regular too.


Index the states of a finite automaton A by positive integers: q1,,qm. Suppose 1i,j,km. Define the language L(i,j,k) as follows: a word is in L(i,j,k) iff it is the label of a path from qi to qj such that each of the intermediate nodes on the path has an index at most k. Now, fix i,j, and do inductionMathworldPlanetmath on k.

  1. 1.

    L(i,j,0) is regular for any i,j. This is so because a word in L(i,j,0) (if it is non-empty) has length at most 1, so that it is either in Σ or λ. In any case, L(i,j,0) is regular.

  2. 2.

    If L(i,j,k) is regular, so is L(i,j,k+1). Let p be a path that begins at qi and ends at qj such that all of its intermediate nodes have indices no more than k+1. Then either none of the nodes have indices more than k, or qk+1 is an intermediate node. In the later case, p begins at qi, reaches qk+1 for the first time, leaves qk+1, may or may not return to qk+1, until its last return (if it does return), and ends at qj. What we have just described can be put into an identityPlanetmathPlanetmathPlanetmathPlanetmath:


    Since each of the languages on the right hand side is regular (as the last componentMathworldPlanetmath is k in each case), the language on the left hand side is reqular (as it is obtained by performing regular operations on regular languages).

In particular, L(i,j,m) is regular. Since L(A)={L(i,j,m)qiI,qjF}, a finite union of regular languages, L(A) is regular as well. ∎

Remark. Kleene’s theorem can be generalized in at least two ways. By realizing that an automaton is just a directed graph whose edges are labeled by elements of Σ*, a finitely generatedMathworldPlanetmathPlanetmath free monoid, one may define a finite automaton over an arbitrary monoid. For more details, see this entry (http://planetmath.org/AutomatonOverAMonoid). The other is to generalize the notion of a word from finite to infiniteMathworldPlanetmath, and modify the notion of acceptance so infinite words may be accepted.

Title Kleene’s theorem
Canonical name KleenesTheorem
Date of creation 2013-03-22 19:01:37
Last modified on 2013-03-22 19:01:37
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 7
Author CWoo (3771)
Entry type Theorem
Classification msc 03D10
Classification msc 68Q05
Classification msc 68Q42
Related topic RegularLanguage