Boolean operations on automata

A Boolean operation is any one of the three set-theoretic operationsMathworldPlanetmath: union, intersectionMathworldPlanetmath, and complementation. Boolean operations on automata are operations defined on automata resembling those from set theoryMathworldPlanetmath.

Union of Two Automata

If A1=(S1,Σ,δ1,I1,F1) and A2=(S2,Σ,δ2,I2,F2). Let S,I,F be the disjoint unionsMathworldPlanetmath of S1 and S2, I1 and I2, F1 and F2 respectively. For any (s,a)S×Σ, define δ to be

δ(s,a):={δ1(s,a)if sS1,δ2(s,a)if sS2.

The automaton A=(S,Σ,δ,I,F) is called the union of A1 and A2, and is denoted by A1A2. Intuitively, we take the disjoint union of the state diagramsMathworldPlanetmathPlanetmath of A1 and A2, and let it be the state diagram of A.

It is easy to see that L(A1A2)=L(A1)L(A2), and that A1A2 is equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath to A2A1.

If only one starting state is required, one can modify the definition of A1A2 by adding a new state q and setting it as the new start state, then adding an edge from q to each of the states in I with label λ. The modified A1A2 is equivalent to the original A1A2. Furthermore, if A1 and A2 are DFA’s, so is A1A2.

Complement of an Automaton

Let A=(S,Σ,δ,I,F) be an automaton. We define the complement A of A as the quintuple


where F=S-F. It is clear that A is a well-defined automaton. Additionally, A is finite iff A is, and A is deterministicMathworldPlanetmath iff A is.

Visually, the state diagram of A is a directed graphMathworldPlanetmath whose final nodes are exactly the non-final nodes of A.

It is obvious that (A)=A and that A is a DFA iff A is.

Suppose A is a DFA. Then it is easy to see that a string aΣ* is accepted by A precisely when a is rejected by A. If L(A) denotes the languagePlanetmathPlanetmath consisting of all words accepted by A. Then


where L(A)=Σ*-L(A), the complement of L(A) in Σ*.

However, because it is possible that for some (s,a), δ(s,a)=, the language accepted by an arbitrary automaton A is in general not L(A).

Intersection of Two Autamata

One may define A1A2 to be (A1A2). However, defined this way,


is in general not true.

The way to ensure that the equation above always holds is to define A1A2 via the productPlanetmathPlanetmath of A1 and A2. For more details, see the entry on product of automata.

If both A1 and A2 are DFA’s, then A1A2 is equivalent to (A1A2).

Title Boolean operations on automata
Canonical name BooleanOperationsOnAutomata
Date of creation 2013-03-22 18:03:09
Last modified on 2013-03-22 18:03:09
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 8
Author CWoo (3771)
Entry type Definition
Classification msc 03D05
Classification msc 68Q45
Defines complement of an automaton
Defines union of automata