juxtaposition of automata


Let A=(S1,Σ1,δ1,I1,F1) and B=(S2,Σ2,δ2,I2,F2) be two automata. We define the juxtaposition of A and B, written AB, as the sextuple (S,Σ,δ,I,F,ϵ), as follows:

  1. 1.

    S:=S1S1, where denotes disjoint unionMathworldPlanetmath,

  2. 2.

    Σ:=(Σ1Σ2){ϵ},

  3. 3.

    δ:S×ΣP(S) given by

    • δ(s,ϵ):=I2 if sF1, and δ(s,ϵ):={s} otherwise,

    • δ|(S1×Σ1):=δ1,

    • δ|(S2×Σ2):=δ2, and

    • δ(s,α):= otherwise (where αϵ).

  4. 4.

    I:=I1,

  5. 5.

    F:=F2.

Because S1 and S2 are considered as disjoint subsets of S, IF=. Also, from the definition above, we see that AB is an automaton with ϵ-transitions (http://planetmath.org/AutomatonWithEpsilonTransitions).

The way AB works is as follows: a word c=ab, where aΣ1* and bΣ2*, is fed into AB. AB first reads a as if it were read by A, via transition function δ1. If a is accepted by A, then one of its accepting states will be used as the initial state for B when it reads b. The word c is accepted by AB when b is accepted by B.

Visually, the state diagramMathworldPlanetmathPlanetmath GA1A2 of A1A2 combines the state diagram GA1 of A1 with the state diagram GA2 of A2 by adding an edge from each final node of A1 to each of the start nodes of A2 with label ϵ (the ϵ-transition).

Proposition 1.

L(AB)=L(A)L(B)

Proof.

Suppose c=ab is a words such that aΣ1* and bΣ2*. If cL(AB), then δ(q,aϵb)F for some qI=I1. Since δ(q,aϵb)F2=δ(q,aϵb)F and bΣ2*, we have, by the definition of δ, that δ(q,aϵb)=δ(δ(q,aϵ),b)=δ2(δ(q,aϵ),b), which shows that bL(B) and δ(q,aϵ)I2. But δ(q,aϵ)=δ(δ(q,a),ϵ), by the definition of δ again, we also have δ(q,a)F1, which implies that δ(q,a)=δ1(q,a). As a result, aL(A).

Conversely, if aL(A) and bL(B), then for any qI=I1, δ(q,a)=δ1(q,a), which has non-empty intersectionMathworldPlanetmath with F1. This means that δ(q,aϵ)=δ(δ(q,a),ϵ)=I2, and finally δ(q,aϵb)=δ(δ(q,aϵ),b)=δ(I2,b), which has non-empty intersection with F2=F by assumptionPlanetmathPlanetmath. This shows that aϵbL((AB)ϵ), or abL(AB). ∎

Title juxtaposition of automata
Canonical name JuxtapositionOfAutomata
Date of creation 2013-03-22 18:03:51
Last modified on 2013-03-22 18:03:51
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 14
Author CWoo (3771)
Entry type Definition
Classification msc 03D05
Classification msc 68Q45