Automata and Forbidden Words^{∗}

M. Crochemore^{†}  F. Mignosi^{‡}  A. Restivo^{§}

October 28, 1998

Abstract Let L(M) be the (factorial) language avoiding a given anti-factorial language M. We design an automaton accepting L(M) and built from the language M. The construction is effective if M is finite.

If M is the set of minimal forbidden words of a single word v, the automaton turns out to be the factor automaton of v (the minimal automaton accepting the set of factors of v).

We also give an algorithm that builds the trie of M from the factor automaton of a single word. It yields a non-trivial upper bound on the number of minimal forbidden words of a word.

Keywords: formal languages, factorial language, anti-factorial language, factor code, factor automaton, forbidden word, avoiding a word, failure function.

1 Introduction

Let L ⊆ A^{∗} be a factorial language, i.e., a language containing all factors of its words. A word w ∈ A^{∗} is called a minimal forbidden word for L if w ∉ L and all proper factors of w belong to L. We denote by MF (L) the language of minimal forbidden words for L.

The study of combinatorial properties of MF (L) helps investigate the structure of the language L or of the system it describes. For instance, locally testable factorial languages (cf [8]) are characterized by the fact that the corresponding languages of minimal forbidden words are finite. In the context of Symbolic Dynamics they correspond to systems of finite type.

Another example is given by a language L that is the set of factors of an infinite word: in this case, as shown in [2], the elements of MF (L) are closely related to the bispecial factors (cf. [6], [7] and [3]) of the infinite word.

∗A preliminary version of this work has been accepted to MFCS’98

†Institut Gaspard-Monge, mac@univ-mlv.fr. Work by this author is supported in part by Programme “Génomes” of C.N.R.S.

‡Università di Palermo, mignosi@altair.math.unipa.it.

§Università di Palermo, restivo@altair.math.unipa.it.

A measure of complexity of the language L is introduced in [2] based on the function F_{L}, that counts, for any n, the number of words of length n in MF (L). Authors prove that the growth of F_{L}(n) as well as the topological entropy of MF (L) are topological invariants of the dynamical system defined by L. This result provides a usefull tool to show that some systems are not isomorphic, which comes in addition to other notions like the ordinary notion of entropy and the zeta function, for example.

Finally, [5] considers properties of languages defined by finite forbidden sets of words. Authors define the Möbius function for these languages.

In this paper we focus on the transformations between L and MF (L). We first design an automaton accepting L and that is built from the language M = MF (L). When M is a finite set the transformation is effective. Moreover, if M is given by its digital tree, that is, its tree-like deterministic automaton, the algorithm is very similar to the algorithm of Aho and Corasick that builds a pattern-matching machine for a finite set of words [1].

In a second part we consider the particular situation of a language that is the set of factors of a single word v. The construction of its factor automaton, the minimal deterministic automaton accepting the factors of v (see [4]) is known to be rather intricate. It is remarkable that the preceding transformation yields exactly the factor automaton of v when the input if the set M of minimal forbidden words of v. We also give an algorithm that realizes the converse transformation, building the trie of M from the factor automaton of v. A corollary of the algorithm is a non-trivial upper bound on the number of minimal forbidden words of a word.

The complexities of algorithms described in this paper are all linear in the size of their input or output. Therefore, the design of possible faster algorithms relies on different representations of objects, which is not the aim of the paper.

2 Avoiding an anti-factorial language

Let A be a finite alphabet and A^{∗} be the set of finite words drawn from the alphabet A, the empty word ϵ included. Let L ⊆ A^{∗} be a factorial language, i.e. a language satisfying: ∀u, v ∈ A^{∗} uv ∈ L ⟹ u, v ∈ L. The complement language L^{c} = A^{∗} \ L is a (two-sided) ideal of A^{∗}. Denote by MF (L) the base of this ideal, we have L^{c} = A^{∗}MF (L)A^{∗}.

The set MF (L) is called the set of minimal forbidden words for L. A word v ∈ A^{∗} is forbidden for the factorial language L if v ∉ L, which is equivalent to say that v occurs in no word of L. In addition, v is minimal if it has no proper factor that is forbidden.

One can note that the set MF (L) uniquely characterizes L, just because

L = A^{∗} \ A^{∗}MF (L)A^{∗}.  (1)

The following simple observation provides a basic characterization of minimal forbidden words.

Remark 1 A word v = a_{1}a_{2} ⋯ a_{n} belongs to MF (L) iff the two conditions hold:

• v is forbidden, (i.e., v ∉ L),

• both a_{1}a_{2} ⋯ a_{n−1} ∈ L and a_{2}a_{3} ⋯ a_{n} ∈ L (the prefix and the suffix of v of length n − 1 belong to L).

The remark translates into the equality:

MF (L) = AL ∩ LA ∩ (A^{∗} \ L).  (2)

As a consequence of both equalities (1) and (2) we get the following proposition.

Proposition 1 For a factorial language L, languages L and MF (L) are simultaneously rational, that is, L ∈ Rat(A^{∗}) iff MF (L) ∈ Rat(A^{∗}).

The set MF (L) is an anti-factorial language or a factor code, which means that it satisfies: ∀u, v ∈ MF (L) u ≠ v ⟹ u is not a factor of v, property that comes from the minimality of words of MF (L).

We introduce a few more definitions.

Definition 1 A word v ∈ A^{∗} avoids the set M, M ⊆ A^{∗}, if no word of M is a factor of v, (i.e., if v ∉ A^{∗}MA^{∗}). A language L avoids M if every word of L avoids M.

From the definition of MF (L), it readily comes that L is the largest (according to the subset relation) factorial language that avoids MF (L). This shows that for any anti-factorial language M there exists a unique factorial language L(M) for which M = MF (L). The next remark summarizes the relation between factorial and anti-factorial languages.

Remark 2 There is a one-to-one correspondence between factorial and antifactorial languages. If L and M are factorial and anti-factorial languages respectively, both equalities hold: MF (L(M)) = M and L(MF (L)) = L.

We also refer to the next definition that is to be considered in the context of dynamical systems (see [9] for example).

Definition 2 The factorial language L is said to be of finite type when MF (L) is finite.

Finally, with an anti-factorial finite language M we associate the finite automaton A(M) as described below. The automaton is deterministic and complete, and, as shown at the end of the section by Theorem 3, the automaton accepts the language L(M).

The automaton A(M) is the tuple (Q, A, i, T, F) where • the set Q of states is {w | w is a prefix of a word in M},

• A is the current alphabet,

• the initial state i is the empty word ϵ,

• the set T of terminal states is Q \ M.

States of A(M) that are words of M are sink states. The set F of transitions is partitioned into the three (pairwise disjoint) sets F_{1}, F_{2}, and F_{3} defined by:

• F_{1} = {(u, a, ua) | ua ∈ Q, a ∈ A} (forward edges or tree edges),

• F_{2} = {(u, a, v) | u ∈ Q \ M, a ∈ A, ua ∉ Q, v longest suffix of ua in Q} (backward edges),

• F_{3} = {(u, a, u) | u ∈ M, a ∈ A} (loops on sink states).

The transition function defined by the set F of arcs of A(M) is noted δ.

Remark 3 One can easily prove from definitions that

1. if q ∈ Q \ (M ∪ {ϵ}), all transitions arriving on state q are labeled by the same letter a ∈ A,

2. from any state q ∈ Q we can reach a sink state, i.e., q can be extended to a word of M.

Definition 3 For any v ∈ A^{∗}, q_{v} denotes the state δ(ϵ, v), target of the unique path in A(M) starting at the initial state and labeled by v.

Since A(M) is a complete automaton, q_{v} is always defined. In the automaton A(M) states are words, but to avoid misunderstandings we sometimes write “the word corresponding to q_{v}” instead of just “the word q_{v}”.

Remark 4 Note that if v is a state of A(M) we have q_{v} = v.

We are now ready to state and prove the next lemma that is used in the proof of Theorem 3, the main result of the section.

Lemma 2 Let M be an anti-factorial language and consider A(M). Let v ∈ A^{∗} be such that, for any proper prefix u of v, q_{u} is not a sink state (q_{u} ∉ M). Then,

1. the word q_{v} is a suffix of v,

2. q_{v} is the longest suffix of v that is also a state of A(M)

(or ∀q ∈ Q q suffix of v ⟹ q suffix of q_{v}).

Proof. By induction on |v|.

Base of the induction, |v| = 0. Then, v = ϵ = q_{v} and points 1 and 2 are trivially satisfied.

Inductive step |v| > 0. We can write v = ua, a ∈ A; hence, q_{v} = δ(q_{u}, a) or equivalently (q_{u}, a, q_{v}) ∈ F. By induction, q_{u} is a suffix of u and, if q ∈ Q is a suffix of u, q is also a suffix of q_{u}. By hypothesis, the transition (q_{u}, a, q_{v}) cannot belong to F_{3} because q_{u} is not a sink state. We have two cases:

(i) (q_{u}, a, q_{v}) ∈ F_{1}, (ii) (q_{u}, a, q_{v}) ∈ F_{2}.

In case (i) condition 1 readily comes from the inductive hypothesis because q_{v} = δ(q_{u}, a). Let us suppose that q is a state suffix of v. If q = ϵ then 2 is trivially satisfied; otherwise, if q ≠ ϵ, q = δ(q′, a) for some state q′ ∈ Q. Since v = ua, q′ is a suffix of u and, by induction, q′ is a suffix of q_{u}. Since q_{v} = δ(q_{u}, a) and q (= δ(q′, a)) is a suffix of q_{v}, which proves that 2 is satisfied. In case (ii), since by definition q_{v} is a suffix of δ(q_{u}, a), and since by induction q_{u} is a suffix of u, q_{v} is a suffix of ua = v and 1 holds. If q ∈ Q is a suffix of v with q ≠ ϵ (otherwise 2 trivially holds), then q = q′a for some q′ suffix of u, and by induction q′ is a suffix of q_{u} and moreover q is a suffix of δ(q_{u}, a). By definition q_{v} is the longest suffix of δ(q_{u}, a) that is also a state, and consequently q is a suffix of q_{v}. ▷◁

Denoting by Lang(A) the language accepted by an automaton A, we get the main theorem of the section.

Theorem 3 For any anti-factorial language M, Lang(A(M)) = L(M).

Proof. We first prove L(M) ⊆ Lang(A(M)). We have to show that if v is a word that avoids M then v ∈ Lang(A(M)). Assume ab absurdo that v ∉ Lang(A(M)); therefore q_{v} is a sink state. Let u be the shortest prefix of v for which q_{u} is a sink state (note that q_{u} = q_{v}). By lemma 2 statement 1, q_{u} is a suffix of u, but q_{v} is by definition an element of M, and so v does not avoid M, a contradiction.

We then prove Lang(A(M)) ⊆ L(M). Let v ∈ Lang(A(M)). Let us suppose ab absurdo that v does not avoid M, i.e., v = uwz for some w ∈ M, u, z ∈ A^{∗}. We choose uw as the shortest prefix of v that belongs to A^{∗}M. Since w ∈ M it is by definition a state of A(M); since w is a state that is a suffix of uw, by Lemma 2 statement 2, w is a suffix of q_{uw}. But q_{uw}, which is by definition a state of A(M), is a prefix of an element w′ of M (note that w′ is not empty). Since w is a suffix of a prefix of w′, w is a factor of w′, a contradiction because M is anti-factorial. ▷◁

The above definition of A(M) turns into the algorithm below, called Lautomaton, that builds the automaton from a finite anti-factorial set of words. The input is the trie T that represents M. It is a tree-like automaton accepting the set M and, as such, it is noted (Q, A, i, T, δ′). The procedure can be adapted to test whether T represents an anti-factorial set, or even to generate the trie of the anti-factorial language associated with a set of words.

In view of Equality 1, the design of the algorithm remains to adapt the construction of a pattern matching machine (see [1] or [4]). The algorithm uses a function f called a failure function and defined on states of T as follows. States of the trie T are identified with the prefixes of words in M. For a state au (a ∈ A, u ∈ A^{∗}), f(au) is δ′(i, u), quantity that may happen to be u itself. Note that f(i) is undefined, which justifies a specific treatment of the initial state in the algorithm.

              [figure: 0; 1; 2; 3; 4; a; b; a; b; a; b; b]

Figure 1: Trie of the factor code {aa, bbab, bbb} on the alphabet {a, b}. Squares represent terminal states.

L-automaton (trie T = (Q, A, i, T, δ′))

1. for each a ∈ A

2. if δ′(i, a) defined

3. set δ(i, a) = δ′(i, a);

4. set f(δ(i, a)) = i;

5. else

6. set δ(i, a) = i;

7. for each state p ∈ Q \ {i} in width-first search and each a ∈ A 8. if δ′(p, a) defined

9. set δ(p, a) = δ′(p, a);

10. set f(δ(p, a)) = δ(f(p), a);

11. else if p ∉ T

12. set δ(p, a) = δ(f(p), a);

13. else

14. set δ(p, a) = p;

15. return (Q, A, i, Q \ T, δ);

Example. Figure 1 displays the trie that accepts M = {aa, bbab, bbb}. It is an anti-factorial language. The automaton produced from the trie by algorithm L-automaton is shown in Figure 2. It accepts the prefixes of (ab ∪ b)(ab)^{∗}ba that are all the words avoiding M.

Theorem 4 Let T be the trie of an anti-factorial language M. Algorithm Lautomaton builds a complete deterministic automaton accepting L(M).

Proof. The automaton produced by the algorithm has the same set of states as the input trie. It is clear that the automaton is deterministic and complete.

Let u ∈ A^{+} and p = δ(i, u). A simple induction on |u| shows that the word corresponding to f(p) is the longest proper suffix of u that is a prefix of some word in M. This notion comes up in the definition of the set of transitions F_{2} in the automaton A(M). Therefore, the rest of the proof just remains to check that instructions implement the definition of A(M). ▷◁

              [figure: 0; 1; 2; 3; 4; a; b; a; b; b; a; a; b; b; a; a,b; a,b; a,b]

Figure 2: Automaton accepting the words that avoid the set {aa, bbab, bbb}. Squares represent non-terminal states (sink states).

Proposition 5 Algorithm L-automaton runs in time O(|Q| × |A|) on input T = (Q, A, i, T, δ′) if transition functions are implemented by transition matrices.

Proof. If transition functions δ and δ′ are implemented by transition matrices, access to or definition of δ(p, a) or δ′(p, a) (p state, a ∈ A) are realized in constant amount of time. The result follows immediately. ▷◁

3 Factor automaton of a single word

In this section we specialize the previous results to the language of factors of a single word. It is proved below that the contruction of Section 2 yields the factor automaton (minimal deterministic automaton accepting the factors) of the word (see Theorem 7). The minimality of the automaton seems to be exceptional because, for example, the same construction applied to the set {aa, ab} does not provide a minimal automaton.

The reverse construction that produces the trie of minimal forbidden words from the factor automaton is described in the next section.

We consider a fixed word v ∈ A^{∗} and denote by F(v) the language of factors of v.

Proposition 6 The language F(v) is of finite type.

Proof. Indeed, factors of v, of lengths less than |v|+1, avoid all words of length exactly |v| + 1. Therefore, every minimal forbidden word of F(v) has length at most |v| + 1. ▷◁

For instance, for the word v = abbab, the set of minimal forbidden words of F(abbab) is {aa, aba, babb, bbb, c} (see Figures 3 and 4).

The result of the previous proposition is made more precise in the next section, but an immediate consequence of it and of the definition of the automaton A(M) for an anti-factorial language M, the automaton A(MF (F(v))) has a finite number of states. The next statement gives a complete characterization of the automaton as the factor automaton of v.

Theorem 7 For any v ∈ A^{∗}, the automaton obtained from A(MF (F(v))) by removing its sink states is the minimal deterministic finite automaton accepting the language F(v) of factors of v.

Proof. The automaton A(MF (F(v))) is already a deterministic finite automaton that accepts the language F(v) by Theorem 3. We only have to prove that it is minimal after removing the sink states.

Suppose ab absurdo that there exist two equivalent non-sink states p, q in Q. By the standard equivalence relation of undistinginshability and by construction p, q ∈ F(v). Hence, v = xpy and v = x′qy′ and we can choose x and x′ of minimal length. We consider two cases:

(i) |xp| ≠ |x′q|, (ii) |xp| = |x′q|.

Case (i). We can suppose for example that |xp| < |x′q| (the case |xp| > |x′q| is handled symmetrically). Then, xpy ∈ F(v) implies that δ(p, y) is not a sink state, hence, by the equivalence δ(q, y) is not a sink state, that is, qy ∈ F(v) by Remark 4. Therefore, v = x”qyz where |x”| ≥ |x′| by the choice of x′ (of minimal length). Hence, |v| ≥ |x′| + |q| + |y| + |z| > |xp| + |y| = |v|, a contradiction. Case (ii). The equality |xp| = |x′q| implies either that p is a suffix of q or the converse. Let us suppose for example that p = sq for some word s ≠ ϵ. By Remark 3 statement 2, there exists w = pz that belongs to MF (F(v)). By the equivalence, qz is also a sink state and, again by the equivalence, for no proper prefix u of qz, q_{u} is a sink state. Hence, by Lemma 2.1, q_{qz} is an element of MF (F(v)), that is, a suffix of qz. Since p = sq, s ≠ ϵ, q_{qz} is a proper suffix of pz against the anti-factorial property of MF (F(v)). A contradiction again.

After cases (i) and (ii) it appears that there cannot exist two different nonsink states p, q in Q that are equivalent. Therefore the automaton without sink states is minimal, which ends the proof. ▷◁

The property stated by Theorem 7 does not generalize to any finite set words. For example, consider the set M = {aa, ba}. Its trie has three internal nodes and then the automaton A(M) has three states after removing sink states. But the language L(M) is b^{∗} + ab^{∗} and its minimal automaton has only two states.

4 Minimal forbidden words of a word

We end the article by an algorithm that builds the trie accepting the language MF (F(v)) of minimal words avoided by v. This is an implementation of the

         [figure: 0; 1; 2; 3; 4; 6; 5; a; b; b; a; b; b; b; a]

Figure 3: Factor automaton of abbab; all states are terminal.

     [figure: 0; 1; 2; 3; 4; 6; 5; a; b; b; b; b; a; c; a; a; b; b]

Figure 4: Trie of minimal forbidden words of F(abbab) on the alphabet {a, b, c}. Squares represent terminal states.

inverse of the transformation described in Section 2. Its design follows Equality 2. A corollary of the transformation gives a bound on the number of minimal forbidden words of a single word, which improves on the bound coming readily from Proposition 6.

MF-trie (factor automaton A = (Q, A, i, T, δ) and its suffix function s)

1. for each state p ∈ Q in width-first search from i and each a ∈ A

2. if δ(p, a) undefined and (p = i or δ(s(p), a) defined)

3. set δ′(p, a) = new sink;

4. else if δ(p, a) = q and q not already treated

5. set δ′(p, a) = q;

6. return (Q, A, i, {sinks}, δ′);

The input of algorithm MF-trie is the factor automaton of word v. It is the minimal deterministic automaton accepting the factors of v. It includes the failure function defined on the states of the automaton and called s. This function is a by-product of efficient algorithms that build the factor automaton (see [4]). It is defined as follows. Let u ∈ A^{+} and p = δ(i, u). Then, s(p) = δ(i, u′) where u′ is the longest suffix of u for which δ(i, u) ≠ δ(i, u′). It can be shown that the definition of s(p) does not depend on the choice of u.

Example Consider the word v = abbab on the alphabet {a, b, c}. Its factor automaton is displayed in Figure 3. The failure function s defined on states has values: s(1) = s(5) = 0, s(2) = s(3) = 5, s(4) = 1, s(6) = 2. Algorithm MF-trie produces the trie of Figure 4 that represents the set of five words

{aa, aba, babb, bbb, c}.

Theorem 8 Let A be the factor automaton of a word v ∈ A^{∗}. (It accepts the language F(v).) Algorithm MF-trie builds the tree-like deterministic automaton accepting the set of minimal forbidden words of F(v), that is MF (F(v)).

Proof. The transitions defined at line 5 duplicates the transition of the widthfirst search tree, which is the tree of shortest paths from the the initial state of A. This fact is used in the proof. All other transitions are created at line 3 and lead to a sink state. Let A′ be the automaton produced by the algorithm.

Consider a word ua (a ∈ A) accepted by A′. (A′ accepts only non-empty words.) Let p = δ′(i, u). By the remark above, u is the shortest word for which δ(i, u) = p. Therefore, if u = by with b ∈ A, we have δ(i, y) = s(p) by definition of the suffix function s. When the test “δ(s(p), a) defined” is satisfied, this implies that ya ∈ F(v). Thus, bya ∉ F(v), while by, ya ∈ F(v). So, after Remark 1, bya = ua is a minimal forbidden word for F(v).

If u is the empty word, p = i. The transition from i to the sink labeled by a is created under the condition “δ(p, a) undefined”, which means that the letter a does not occur in v. The word a is again a minimal forbidden word for F(v) in this case.

This proves that any word accepted by A′ is in MF (F(v)).

Conversely, let ua ∈ MF (F(v)). If u is the empty word, this means that a does not occur in v, therefore there is no transition labeled by a in A. Lines 3 and 4 cope with this situation by creating a δ′-transition from the initial state to accept a.

Assume now that u = by with b ∈ A. The word u is a factor of v, so let p = δ(i, u). Note that u is the shortest word for which p = δ(i, u), because all such words are suffixes of each others in the factor automaton A. The word ua is not a factor of v, so the condition “δ(p, a) undefined” is satisfied. Let q = s(p). We have q = δ(i, y) because of the minimality of length of u and the definition of s. By the choice of ua = bya, ya is a factor of v. Thus, the condition “δ(s(p), a) defined” at line 3 is satisfied which yields the creation of a transition at line 4 to make A′ accept ua as wanted.

This ends the whole proof. ▷◁

Corollary 9 A word v ∈ A^{∗} has no more than 2(|v|−2)(|A_{v}|−1)+|A| minimal forbidden words if |v| ≥ 3, where A_{v} is the set of letters occurring in v. The bound becomes |A| + 1 if |v| < 3.

Proof. The number of words in MF (F(v)) is the number of sink states created during the execution of algorithm MF-trie. These states have exactly one ingoing arc originated at a state of the factor automaton A of v. So, we have to count these arcs.

From the initial state of A there is exactly |A| − |A_{v}| such arcs. From the (unique) state of A without outgoing arc, there are at most |A_{v}| such arcs. From other states there are at most |A_{v}| − 1 such arcs.

For |v| ≥ 3, it is known that A has at most 2|v|−2 states (see [4]). Therefore, |MF (F(v))| ≤ (|A|−|A_{v}|)+|A_{v}|+(2|v|−4)(|A_{v}|−1) = 2(|v|−2)(|A_{v}|−1)+|A|.

When |v| < 3, it can be checked directly that |MF (F(v))| ≤ |A| + 1. ▷◁

Proposition 10 Algorithm MF-trie runs in time O(|v| × |A|) on input word v if transition functions are implemented by transition matrices.

Proof. As for the proof of Proposition 5, the hypothesis on implementation implies that the running time of the algorithm is proportional to |Q| × |A|. Thus, the result is a consequence of the linear size of A: the factor automaton of v has no more than 2|v| states (see [4] for instance). ▷◁

References

[1] A. V. Aho and M. J. Corasick. Efficient string matching: an aid to bibliographic search, Comm. ACM 18:6 (1975) 333–340.

[2] M.-P. Béal, F. Mignosi, and A. Restivo. Minimal Forbidden Words and Symbolic Dynamics, in (STACS’96, C. Puech and R. Reischuk, eds., LNCS 1046, Springer, 1996) 555–566.

[3] J. Cassaigne. Complexité et Facteurs Spéciaux, Bull. Belg. Math. Soc. 4 (1997) 67–88.

[4] M. Crochemore, C. Hancart. Automata for matching patterns, in (Handbook of Formal Languages, G. Rozenberg, A. Salomaa, eds.”, Springer-Verlag”, 1997, Volume 2, Linear Modeling: Background and Application) Chapter 9, 399–462.

[5] V. Diekert, Y. Kobayashi. Some identities related to automata, determinants, and Möbius functions, Report 1997/05, Fakultät Informatik, Universität Stuttgart, 1997.

[6] A. de Luca, F. Mignosi. Some Combinatorial Properties of Sturmian Words, Theor. Comp. Sci. 136 (1994) 361–385.

[7] A. de Luca, L. Mione. On Bispecial Factors of the Thue-Morse Word, Inf. Proc. Lett. 49 (1994) 179–183.

[8] R. McNaughton, S. Papert. Counter-Free Automata, M.I.T. Press, MA 1970.

[9] D. Perrin. Symbolic Dynamics and Finite Automata, invited lecture in (Proc. MFCS’95, LNCS 969, Springer, Berlin 1995).