One may also want to construct a machine that accepts the complement
of the set of strings a given machine accepts. This turns out to be
possible and reasonably easy to do, once we straighten out a minor
issue. Up to now we have been mostly ignoring the alphabet of symbols
that make up the strings. This has been fine for accepting strings,
since if a symbol never appears in any transition, the machine can
never accept any string containing that symbol. But when we talk
about strings that a machine rejects, we have to give the alphabet
with respect to which to take the complement. For example, what is
the complement of the language that consists of all strings consisting
of only *a*'s and *b*'s? It is the empty set if the alphabet is
,
but if the alphabet is ,
then it is the set of
all strings over
that contain at least one *c*.

Using our current representation, we will assume that the alphabet of
a given machine is the set of symbols that appear on *some*
transition of that machine. While this seems to be a reasonable
assumption, note that it could be incorrect for the second example of
the complement of all strings of *a*'s and *b*'s given above. (If we
were committed to being very precise, we could add an XSB relation
which for each machine defined the set of symbols in its alphabet.)

The basic idea for generating the complement machine is simply to take
the original machine but to take the complement of its final states to
the be final states of the complement-accepting machine. But there
are a couple of things we have to guarantee before this works. First
the original machine must be deterministic, since otherwise for a
given string it might end in both a final and a nonfinal state. In
this case it should be rejected by the machine accepting the
complement language, but simply inverting the final and nonfinal
states would result in it being accepted. So we will always start
with a deterministic machine. Second, we have to be sure that the
machine gets to some state on *every* input. That is, there must
always be a transition that can be taken, regardless of the symbol
being scanned. That is, every state must have an outgoing transition
for every symbol in the alphabet. And here is where the importance of
the alphabet is clear.

So we will separate our construction into two parts: first we will complete the machine (assuming it is deterministic) by adding transitions to a new state, called ``sink,'' when there are no transitions on some symbols; and second we will complement a completed machine.

% completed machine % A symbol is in the alphabet of a machine if it appears in a non-epsilon % transition. (Note that this is our convention and for some machines % could be wrong.) alphabet(Mach,Sym) :- m(Mach,_,Sym,_), Sym \== ''. % S is a (possibly reachable) state in machine if it's initial or has an % incoming edge. is_state(Mach,S) :- m(Mach,_,_,S). is_state(Mach,S) :- mis(Mach,S). % The initial states and final states of the completed machine are the % same as the original machine. mis(completed(Mach),IS) :- mis(Mach,IS). mfs(completed(Mach),FS) :- mfs(Mach,FS). % Assume Mach is deterministic % There is a transition to ``sink'' if there is no other transition on % this symbol from this state. m(completed(Mach),So,Sy,sink) :- is_state(Mach,So), alphabet(Mach,Sy), tnot(isatransition(Mach,So,Sy)). % Machine transitions from sink to sink on every symbol m(completed(Mach),sink,Sy,sink) :- alphabet(Mach,Sy). % Otherwise the same as underlying machine m(completed(Mach),So,Sy,Ta) :- m(Mach,So,Sy,Ta). % There is a transition if there's a state it transits to. isatransition(Mach,So,Sy) :- m(Mach,So,Sy,_).

Now given a completed machine, we can easily generate the complement machine simply by interchanging final and nonfinal states:

% complement machine % Asume machine is completed and deterministic. % The transitions of the complement machine are the same. m(complement(Mach),So,Sy,Ta) :- m(Mach,So,Sy,Ta). % The initial state of the complement machine is the same. mis(complement(Mach),S) :- mis(Mach,S). % A state is a final state of the complement if it is NOT the final state % of the underlying machine. mfs(complement(Mach),S) :- is_state(Mach,S), tnot(mfs(Mach,S)).

With these definitions, we can compute the complement of our simple machine m0s1s2s:

| ?- [automata]. [automata loaded] yes | ?- m(complement(completed(det(efree(m0s1s2s)))),S,Sy,T), writeln(m(complement(m0s1s2s),S,Sy,T)),fail. m(complement(m0s1s2s),[q2],1,sink) m(complement(m0s1s2s),[q2],0,sink) m(complement(m0s1s2s),[q1,q2],0,sink) m(complement(m0s1s2s),sink,2,sink) m(complement(m0s1s2s),sink,1,sink) m(complement(m0s1s2s),sink,0,sink) m(complement(m0s1s2s),[q1,q2],2,[q2]) m(complement(m0s1s2s),[q1,q2],1,[q1,q2]) m(complement(m0s1s2s),[q0,q1,q2],2,[q2]) m(complement(m0s1s2s),[q0,q1,q2],1,[q1,q2]) m(complement(m0s1s2s),[q0,q1,q2],0,[q0,q1,q2]) m(complement(m0s1s2s),[q2],2,[q2]) m(complement(m0s1s2s),[q0],2,[q2]) m(complement(m0s1s2s),[q0],1,[q1,q2]) m(complement(m0s1s2s),[q0],0,[q0,q1,q2]) no | ?- mis(complement(completed(det(efree(m0s1s2s)))),S), writeln(mis(complement(m0s1s2s),S)),fail. mis(complement(m0s1s2s),[q0]) no | ?- mfs(complement(completed(det(efree(m0s1s2s)))),S), writeln(mfs(complement(m0s1s2s),S)),fail. mfs(complement(m0s1s2s),sink) no | ?-

Given these definitions, we can now write a specification that determines when two machines accept the same language. With complement and intersection, we can define subset: . We leave it as an exercise for the reader to write and test such a specification.