Kleene star of an automaton

Let A=(S,Σ,δ,I,F) be an automaton. Define the Kleene star A* of A as an automaton with ϵ-transitions (http://planetmath.org/AutomatonWithEpsilonTransitions) (S1,Σ,δ1,I1,F1,ϵ) where

  1. 1.

    S1=S{q} (we either assume that q is not a symbol in Σ, or we take the disjoint unionMathworldPlanetmath)

  2. 2.

    δ1 is a function from S1×(Σ{ϵ}) to P(S1) given by:

    • δ1(s,ϵ):=I if s=q, δ1(s,ϵ):={q} for any sF,

    • δ1(s,α):=δ(s,α), for any (s,α)S×Σ, and

    • δ1(s,α):= otherwise.

  3. 3.


Basically, we throw into A* all transitions in A. In addition, we add to A* transitions taking s to any initial states of A, as well as transitions taking any final states of A to s. Visually, the state diagramMathworldPlanetmathPlanetmath GA* of A* is obtained by adding a node q to the state diagram GA of A, and making q both the start and the final node of GA*. Furthermore, add edges from q to the start nodes of GA, and edges from the final nodes of GA to q, and let ϵ be the label for all of the newly added edges.

Proposition 1.



Clearly λL(A)*. In addition, since I1=F1, λL(Aϵ*)=L(A*). This proves the case when the word is empty. Now, we move to the case when the word has non-zero length.

  • L(A)*L(A*).

    Suppose a=a1a2an is a word such that aiL(A), then we claim that b=b1b2bn, where bi=ϵaiϵ, is accepted by Aϵ*. This can be proved by inductionMathworldPlanetmath on n:

    1. (a)

      First, n=1. Then


      Since a1 is accepted by A, δ1(I,a1)=δ(I,a1) contains an accepting state sF, so that


      Hence b1 is accepted by Aϵ*.

    2. (b)

      Next, suppose that given b=b1bn, the subword b1bn-1 (induction step) is accepted by Aϵ*. This means that qδ1(q,b1bn-1), so that


      But δ1(q,bn) contains q as was shown in step 1 above. As a result, b1bn is accepted by Aϵ*.

    This shows that L(A)*L(A*).

  • L(A*)L(A)*.

    Suppose now that a is a word over Σ accepted by A*. This means that, for some ij, j=0,1,,n, the word


    is accepted by Aϵ*, where each aj is a word over Σ with a=a1an. We want to show that each aj is accepted by A.

    The main thing is to notice is that if qδ1(J,ϵi) and JS, where i is a positive integer, then J must contain a state in F. Otherwise, JS-F, so that δ1(J,ϵ)=, and we must have δ1(J,ϵi)=δ1(δ1(J,ϵ),ϵi-1)=δ1(,ϵi-1)=.

    Set J=δ1(q,ϵi0a1ϵi1ϵin-1an) and K=δ1(q,ϵi0a1ϵi1ϵin-1). Then J=δ1(K,an)=δ(K,an)S. Furthermore, by assumptionPlanetmathPlanetmath qδ1(q,b)=δ1(J,ϵin). Therefore, J must contain a state in F. Thus, an is accepted by A. The fact that the remaining ai’s are accepted by A is proved inductively.

    This shows that L(A*)L(A)*.

This completesPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath the proof. ∎

Title Kleene star of an automaton
Canonical name KleeneStarOfAnAutomaton
Date of creation 2013-03-22 18:04:06
Last modified on 2013-03-22 18:04:06
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 16
Author CWoo (3771)
Entry type Definition
Classification msc 03D05
Classification msc 68Q45