Minimal cover-automata for finite languages.
A cover-automaton A of a finite language L &Sgr; is a finite deterministic automaton (DFA) that accepts all words in L and possibly other words that are longer than any word in L. A minimal deterministic finite cover automaton (DFCA) of a finite language L usually has a smaller size than a minimal DFA that accepts L. Thus, cover automata can be used to reduce the size of the representations of finite languages in practice. In this paper, we describe an efficient algorithm that, for a given DFA accepting a finite language, constructs a minimal deterministic finite cover-automaton of the language. We also give algorithms for the boolean operations on deterministic cover automata, i.e., on the finite languages they represent.
Introduction
Regular languages and finite automata are widely used in many areas such as
lexical analysis, string matching, circuit testing, image compression, and parallel
processing. However, many applications of regular languages use actually
only finite languages. The number of states of a finite automaton that accepts
a finite language is at least one more than the length of the longest word in
the language, and can even be in the order of exponential to that number.
If we do not restrict an automaton to accept the exact given finite language
but allow it to accept extra words that are longer than the longest word in
the language, we may obtain an automaton such that the number of states
This research is supported by the Natural Sciences and Engineering Research
Council of Canada grants OGP0041630.
Preprint submitted to Elsevier Preprint
is significantly reduced. In most applications, we know what is the maximum
length of the words in the language, and the systems usually keep track of the
length of an input word anyway. So, for a finite language, we can use such an
automaton plus an integer to check the membership of the language. This is
the basic idea behind cover automata for finite languages.
Informally, a cover-automaton A of a finite language L ' \Sigma   is a finite automaton
that accepts all words in L and possibly other words that are longer
than any word in L. In many cases, a minimal deterministic cover automaton
of a finite language L has a much smaller size than a minimal DFA that accept
L. Thus, cover automata can be used to reduce the size of automata for finite
languages in practice.
Intuitively, a finite automaton that accepts a finite language (exactly) can be
viewed as having structures for the following two functionalities:
(1) checking the patterns of the words in the language, and
(2) controlling the lengths of the words.
In a high-level programming language environment, the length-control function
is much easier to implement by counting with an integer than by using
the structures of an automaton. Furthermore, the system usually does the
length-counting anyway. Therefore, a DFA accepting a finite language may
leave out the structures for the length-control function and, thus, reduce its
complexity.
The concept of cover automata is not totally new. Similar concepts have
been studied in different contexts and for different purposes. See, for exam-
ple, [1,7,4,10]. Most of previous work has been in the study of a descriptive
complexity measure of arbitrary languages, which is called "automaticity" by
Shallit et al. [10]. In our study, we consider cover automata as an implementing
method that may reduce the size of the automata that represent finite
languages.
In this paper, as our main result, we give an efficient algorithm that, for a
given finite language (given as a deterministic finite automaton or a cover
automaton), constructs a minimal cover automaton for the language. Note
that for a given finite language, there might be several minimal cover automata
that are not equivalent under a morphism. We will show that, however, they
all have the same number of states.
Preliminaries
Let T be a set. Then by #T we mean the cardinality of T . The elements of
are called strings or words. The empty string is denoted by -. If w 2 T
then jwj is the length of x.
We define T
l
is an ordered set, k ? 0, the quasi-lexicographical order on
denoted OE, is defined by: x OE y iff jxj ! jyj or
or y.
We say that x is a prefix of y, denoted x - p y, if
A deterministic finite automaton (DFA) is a quintuple
where \Sigma and Q are finite nonempty sets, q
is the transition function. We can extend ffi from Q \Theta \Sigma to Q \Theta \Sigma   by
We usually denote ffi by ffi.
The language recognized by the automaton A is
Fg. For simplicity, we assume that
In what follows we assume that ffi is a total function, i.e., the automaton
is complete.
Let l be the length of the longest word(s) in the finite language L. A DFA
A such that called a deterministic finite cover-automaton
(DFCA) of L. Let A = (Q; \Sigma; ffi; 0; F ) be a DFCA of a finite language L. We
say that A is a minimal DFCA of L if for every DFCA
of L we have #Q - #Q 0 .
a) q 2 Q is said to be accessible if there exists w 2 \Sigma   such that ffi(0;
b) q is said to be useful (coaccessible) if there exists w 2 \Sigma   such that ffi(q; w) 2
F .
It is clear that for every DFA A there exists an automaton A 0 such that
all the states of A 0 are accessible and at most one of the
states is not useful (the sink state). The DFA A 0 is called a reduced DFA.
3 Similarity sequences and similarity sets
In this section, we describe the L-similarity relation on \Sigma   , which is a generalization
of the equivalence relation jL (x jL y: xz 2 L iff yz 2 L for all
z 2 \Sigma   ). The notion of L-similarity was introduced in [7] and studied in [4]
etc. In this paper, L-similarity is used to establish our algorithms.
Let \Sigma be an alphabet, L ' \Sigma   a finite language, and l the length of the longest
in L. Let x; y 2 \Sigma   . We define the following relations:
(1) x -L y if for all z 2 \Sigma   such that jxzj - l and jyzj - l, xz 2 L iff yz 2 L;
(2) x 6- L y if x -L y does not hold.
The relation -L is called similarity relation with respect to L.
Note that the relation -L is reflexive, symmetric, but not transitive. For exam-
ple, let aabbg. It is clear that aab -L aabb (since
but aab 6- L baa (since for
2 L and
The following lemma is proved in [4]:
be a finite language and x;
The following statements hold:
(1) If x -L y, x -L z, then y -L z.
(2) If x -L y, y -L z, then x -L z.
(3) If x -L y, y6- L z, then x6- L z.
If x 6- L y and y -L z, we cannot say anything about the similarity relation
between x and z.
Example 2 Let x; We may have
y, y -L z and x -L z, or
y, y -L z and x6- L z.
Indeed, if we choose
be a finite language.
(1) A set S ' \Sigma   is called an L-similarity set if x -L y for every pair x; y 2 S.
(2) A sequence of words [x is called a dissimilar sequence of
for each pair
(3) A dissimilar sequence [x called a canonical dissimilar sequence
of L if there exists a partition of \Sigma   such that for each
is a L-similarity set.
(4) A dissimilar sequence [x of L is called a maximal dissimilar
sequence of L if for any dissimilar sequence [y
Theorem 4 A dissimilar sequence of L is a canonical dissimilar sequence of
L if and only if it is a maximal dissimilar sequence of L.
PROOF. Let L be a finite language. Let [x be a canonical dissimilar
sequence of L and the corresponding partition of \Sigma   such
that for each is an L-similarity set. Let [y be an
arbitrary dissimilar sequence of L. Assume that m ? n. Then there are y i and
is a L-similarity
set, y i -L y j . This is a contradiction. Then, the assumption that m ? n is
false, and we conclude that [x is a maximal dissimilar sequence.
Conversely, let [x dissimilar sequence of L. Without loss
of generality we can suppose that jx 1 j - jx n j. For
Note that for each y 2 \Sigma   , y -L x i for at least one
is a maximal dissimilar sequence. Thus, is a
partition of \Sigma   . The remaining task of the proof is to show that each X i ,
set.
We assume the contrary, i.e., for some i, 1 - i - n, there exist
such that y6- L z. We know that x i -L y and x i -L z by the definition of
We have the following three cases: (1) jx
(or or (2), then y -L z by
Lemma 1. This would contradict our assumption. If (3), then it is easy to
prove that y 6- x j and z 6- x j , for all j 6= i, using Lemma 1 and the definition
of X i . Then we can replace x i by both y and z to obtain a longer dissimilar
sequence This contradicts the fact that
is a maximal dissimilar sequence of L. Hence,
y - z and X i is a similarity set.
Corollary 5 For each finite language L, there is a unique number N(L) which
is the number of elements in any canonical dissimilar sequence of L.
Theorem 6 Let S 1 and S 2 be two L-similarity sets and x 1 and x 2 the shortest
words in S 1 and S 2 , respectively. If x 1 -L x 2 then
set.
PROOF. It suffices to prove that for an arbitrary word y 1 and an
arbitrary word y 2 holds. Without loss of generality, we assume
that jx 1 j - jx 2 j. We know that jx 1
we have y 1 -L y 2 (Lemma 1 (1)).
4 Similarity relations on states
it is clear that if
y.
Therefore, we can also define similarity as well as equivalence relations on
states.
be a DFA. We define, for each state
i.e., level(q) is the length of the shortest path from the initial state to q.
If for each q 2 Q, we denote xA
qg, where the minimum is taken according to the quasi-
lexicographical order, and LA Fg. When the automaton
A is understood, we write x q instead of xA (q) and L q instead LA (q).
The length of x q is equal to level(q), therefore level(q) is defined for each
We say that
is equivalent to q in A) if for every w 2 \Sigma   , ffi(s; w) 2 F iff
be a DFCA of a finite language L. Let
jg. We say that p -A q (state p is
L-similar to q in A) if for every w 2 \Sigma -l\Gammam , ffi(p; w) 2 F iff ffi(q; w) 2 F .
be a DFCA of a finite language L. Let
such that ffi(0; y.
PROOF. Let
Choose an arbitrary w 2 \Sigma   such that jxwj - l and jywj - l. Because i - jxj
and j - jyj it follows that jwj - l \Gamma m. Since p -A q we have that ffi(p; w) 2 F
which means that xw 2 L(A)
Hence x -L y.
Lemma be DFCA of a finite language L. Let
that ffi(0;
PROOF. Let x -L y and w 2 \Sigma -l\Gammam . If ffi(p; w) 2 F , then ffi(0; xw) 2 F .
Because x -L y, it follows that ffi(0; yw) 2 F , so ffi(q; w) 2 F . Using the
symmetry we get that p -A q.
Corollary 12 Let A = (Q; \Sigma; ffi; 0; F ) be a DFCA of a finite language L. Let
\Sigma   , such that ffi(0; x 1
then x 2 -L y 2 .
Example 13 If x 1 and y 1 are not minimal, i.e. jx
then the conclusion of Corollary 12 is not true.
3. The following is a DFCA of L and we
\Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi*
a
-a
ja
b'
-@
@
@
@
@R
HY
a
HY
Fig. 1. If x -L y then we do not have always that ffi(0; x) -A ffi (0; y)
have that b -L bab, but b6- L a (ba 2 L, aa 2 L and
Corollary 14 Let A = (Q; \Sigma; ffi; 0; F ) be a DFCA of a finite language L and
If p -A q, and level(p) - level(q) and q 2 F then p 2 F .
Lemma be a DFCA of a finite language L. Let
s; m. The
following statements are true:
(1) If s -A p, s -A q, then p -A q.
(3) If s -A p, p6- A q, then s6- A q.
PROOF. We apply Lemma 1 and Corollary 14.
Lemma be a DFCA of a finite language L. Let
is a L-similarity set.
Therefore ffi(p; w) 2 F , and jwj - l \Gamma m.
Hence, because p -A q, ffi(p; w) 2 F , so w 2 L q " \Sigma -l\Gammam .
Lemma be a DFCA of a finite language L. If
-A q for some
Then we can construct a DFCA A of L such that
ffi(s; a) if ffi(s; a) 6= q;
for each s 2 Q 0 and a 2 \Sigma. Thus, A is not a minimal DFCA of L.
PROOF. It suffices to prove that A 0 is a DFCA of L. Let l be the length of
the longest word(s) in L and assume that
Consider a word w 2 \Sigma -L . We now prove that w 2 L iff
If there is no prefix w 1 of w such that ffi(0; w
is the shortest prefix of w such
that In the remaining, it suffices to prove that ffi 0 (p; w
We prove this by induction on the length of w 2 . First consider the
case
by the construction of A 0 . Thus, . Suppose that
the statement holds for jw
Consider the case that jw 2 . If there does not exist u such that
and u be the shortest
nonempty prefix of w 2 such that ffi(p;
By induction hypothesis,
Lemma A be a DFCA of L and L
x -L y.
PROOF. Let l be the length of the longest word(s) in L. Let x jL 0 y. So,
for each z 2 \Sigma   ; xz 2 L 0 iff yz 2 L 0 . We now consider all words z 2 \Sigma   , such
that j xz j- l and j yz j- l. Since
have xz 2 L iff yz 2 L. Therefore, x -L y by the definition of -L .
Corollary 19 Let A = (Q; \Sigma; ffi; 0; F ) be a DFCA of a finite language L, L
L(A). Then p jA q implies p -A q.
Corollary 20 A minimal DFCA of L is a minimal DFA.
PROOF. Let A = (Q; \Sigma; ffi; 0; F ) be a minimal DFCA of a finite language L.
Suppose that A is not minimal as a DFA for L(A), then there exists
such that p jL 0 q, then p -A q. By Lemma 17 it follows that A is not a
minimal DFCA, contradiction.
Remark 21 Let A be a DFCA of L and A a minimal DFA. Then A may not
be a minimal DFCA of L.
Example 22 We take the DFA's:
a
a
a
@ \Gamma\Psi
a
Automaton A
@ \Gamma\Psi
a
Fig. 2. Minimal DFA is not always a minimal DFCA.
The DFA A in Figure 2 is a minimal DFA and a DFCA of aag but
not a minimal DFCA of L, since the DFA B in Figure 2 is a minimal DFCA
of L.
Theorem 23 Any minimal DFCA of L has exactly N(L) states.
PROOF. Let A = (Q; \Sigma; ffi; 0; F ) be DFCA of a finite language L, and
n.
Suppose that n ? N(L). Then there exist q, such that x p -L x q
(because of the definition of N(L)). Then p -A q by Lemma 14. Thus, A is
not minimal. A contradiction.
Suppose that N(L) ? n. Let [y be a canonical dissimilar sequence
of L. Then there exist
Again a contradiction.
Therefore, we have
5 The construction of minimal DFCA
The first part of this section describe an algorithm that determines the similarity
relations between states. The second part is to construct a minimal
DFCA assuming that the similarity relation between states is known.
An ordered DFA is a DFA where ffi(i; implies that i - j, for all states
letters a. Obviously for such a DFA is the sink state.
5.1 Determining similarity relation between states
The aim is to present an algorithm which determines the similarity relations
between states.
of a finite language L. Define D
Fg, and D
is taken according to the quasi-lexicographical order. If the automaton A is
understood then we write D i and fl s instead of D i (A) and respectively fl s (A).
Lemma of a finite language L, and p 2
PROOF. We can assume that i ! j. Then obviously ffi(p;
j. So, we have that jfl
Lemma accepting L,
. If for all a 2 \Sigma, ffi(p; a) -A ffi(q; a),
then p-A q.
PROOF. Let a 2 \Sigma and ffi(p; a) = r and ffi(q; a) = s. If r -A s then for all jwj,
also have: xA (q)aw 2 L iff xA (s)w 2 L for all w 2 \Sigma   , jwj - l \Gamma jx A (s)j and
Hence xA (p)aw 2 L iff xA (q)aw 2 L, for all w 2 \Sigma   , jwj - l \Gamma
maxfjxA (r)j; jx A (s)jg. Because jx A (r)j - jx A
Since a 2 \Sigma is chosen arbitrary, we conclude that xA (p)w 2 L iff xA (q)w 2 L,
for all w 2 \Sigma   , jwj - l \Gamma maxfjxA (p)j; jx A (q)jg, i.e. xA (p) -A xA (q). Therefore,
by using Lemma 11, we get that p -A q.
Lemma 26 Let accepting L such that
. If there exists
a 2 \Sigma such that ffi(p; a)6- A ffi(q; a), then p6- A q.
PROOF. Suppose that p -A q. Then for all aw 2 \Sigma l\Gammam , ffi(p; aw) 2 F iff
by definition that ffi(p; a) -A ffi(q; a). This is a contradiction.
Our algorithm for determining the similarity relation between the states of a
DFA (DFCA) of a finite language is based on Lemmas 25 and 26. However,
most of DFA (DFCA) do not satisfy the condition of Lemma 26. So, we shall
first transform the given DFA (DFCA) into one that does.
be a DFCA of L. We construct the minimal DFA
for the language \Sigma -l ,
The DFA B will have exact l states.
Now we use the standard Cartesian product construction (see, e.g., [3], for
details) for the DFA
(taking the automata in this order) and we eliminate all inaccessible states.
Obviously, satisfies the condition of Lemma 26.
Lemma 27 For the DFA C constructed above,
PROOF. We have
Lemma 28 For the DFA C constructed above we have (p; q) -C (p; r).
PROOF. If p 2 D \Gamma1 (A), the lemma is obvious. Suppose now that
and q - r. Then r - l so It follows that
Lemma 29 For the DFA C constructed above we have that (#Q \Gamma
PROOF. We have that ffi C
2 FC and
2 FC it follows the conclusion.
Now we are able to present an algorithm, which determines the similarity
relation between the states of C. Note that QC is ordered by that (p A ; pB
. Attaching to each state of C is a
list of similar states. For ff; fi 2 QC , if ff -C fi and ff ! fi, then fi is stored on
the list of similar states for ff.
We assume that reduced (so is the sink
state of A).
(1) Compute
(2) Initialize the similarity relation by specifying:
(a) For all (n \Gamma
(b) For all (n \Gamma
(3) For each D i (C), create a list List i , which is initialized to ;.
(4) For each ff 2 following the reversed order of
QC , do the following:
Assuming ff 2 D i (C).
(a) For each fi 2 List i , if ffi C (ff; a) -C ffi C (fi; a) for all a 2 \Sigma, then ff -C fi.
(b) Put ff on the list List i .
By Lemma 24 we need to determine only the similarity relations between
states of the same D i (C) set. The Step 2(a) follows from Lemma 28, 2(b)
from Lemma 29 and Step 4 from Lemma 15.
Remark 30 The above algorithm has complexity O((n \Theta l) 2 ), where n is the
number of states of the initial DFA (DFCA) and l is the maximum accepted
length for the finite language L.
5.2 The construction of a minimal DFCA
As input we have the above DFA C and, with each ff 2 QC , a set S
fig. The output is
DFCA for L.
We define the following:
while (T 6= ;) do the following:
and
;g.
Note that the constructions of x i above are useful for the proofs in the following
only, where the min (minimum) operator for x i is taken according to the
lexicographical order.
According to the algorithm we have a total ordering of the states QC : (p; q) -
Also, using the construction (i.e. the total order on QC ) it
follows that
Lemma 31 The sequence [x constructed above is a canonical
L-dissimilar sequence.
PROOF. We construct the sets X g. Obviously
it follows that X i is a L-similarity set for all
Let w 2 \Sigma   . Because (S i ) 1-i-m\Gamma1 is a partition of Q, w
is a partition of \Sigma   and therefore a canonical L-dissimilar
sequence.
Corollary 32 The automaton D constructed above is a minimal DFCA for
L.
PROOF. Since the number of states is equal to the number of elements of
a canonical L-dissimilar sequence, we only have to prove that D is a cover
automaton for L. Let w 2 \Sigma -l . We have that ffi D (0; w) 2 FD iff ffi C ((0; 0); w) 2
(because C
is a DFCA for L).
6 Boolean operations
We shall use similar constructions as in [3] for constructing DFCA of languages
which are a result of boolean operations between finite languages. The
modifications are suggested by the previous algorithm. We first construct the
DFCA which satisfies hypothesis of Lemma 26 and afterwards we can minimize
it using the general algorithm. Since the minimization will follow in a
natural way we shall present only the construction of the necessarily DFCA.
Let A two DFCA of the finite languages L i , l
2.
6.1 Intersection
We construct the following DFA:
lg.
Theorem 33 The automaton A constructed above is a DFA for
PROOF. We have the following relations:
The rest of the proof
is obvious.
6.2 Union
We construct the following DFA:
where r is such that l r = l.
Theorem 34 The automaton A constructed above is a DFA for
PROOF. We have the following relations:
The rest of the proof is obvious.
6.3 Symmetric difference
We construct the following DFA:
f(s;
r is such that l r = l.
Theorem 35 The automaton A constructed above is a DFA for
PROOF. We have the following relations:
or exclusive w
or exclusive w 2 The rest of the proof
is obvious.
6.4 Difference
We construct the following DFA:
Theorem 36 The automaton A constructed above is a DFA for
PROOF. We have the following relations:
and
The rest of the proof is
obvious.
Open Problems
1) Try to find a better algorithm for minimization or prove that any minimization
algorithm has complexity
Find a better algorithm for determining similar states in any DFCA of L.
Find better algorithms for boolean operations on DFCA.



--R

Uniform characterisations of non-uniform complexity measures
"zone"
Regular languages and programming languages
time complexity gap for two-way probabilistic finite-state automata
Two memory bounds for the recognition of primes by automata
Introduction to Automata Theory
Minimal Nontrivial Space Space Complexity of Probabilistic One-Way Turing Machines
Running time to recognise non-regular languages by 2- way probabilistic automata
A class of measures on formal languages
Properties of a Measure of Descriptional Complexity
Theory of Automata
The state complexities of some basic operations on regular languages
Finite Automata: Behaviour and Synthesis
On the State Complexity of Intersection of
Handbook of Formal Languages
--TR
Uniform characterizations of non-uniform complexity measures
Minimal nontrivial space complexity of probabilistic one-way turing machines
time complexity gap for two-way probabilistic finite-state automata
Running time to recognize nonregular languages by 2-way probabilistic automata
On the state complexity of intersection of regular languages
The state complexities of some basic operations on regular languages
Automaticity I
Regular languages
Introduction To Automata Theory, Languages, And Computation
Theory of Automata

--CTR
Martin Kappes , Frank Niener, Succinct representations of languages by DFA with different levels of reliability, Theoretical Computer Science, v.330 n.2, p.299-310, 2 February 2005
Martin Kappes , Chandra M. R. Kintala, Tradeoffs between reliability and conciseness of deterministic finite automata, Journal of Automata, Languages and Combinatorics, v.9 n.2-3, p.281-292, September 2004
finite languages;deterministic cover automata;deterministic finite automata;cover language;finite automata