Computing Small Nondeterministic Finite Automata

Oliver Matz, Andreas Potthoff Institut für Informatik und Praktische Mathematik Christian-Albrechts-Universität Kiel D-24098 Kiel

             e-mail: oma@informatik.uni-kiel.de

Abstract

We study the minimization problem for nondeterministic finite automata. Two approaches are discussed, based on the construction of two versions of “canonical” automata (for a given regular language), in which minimal automata occur as subautomata. We introduce a heuristic for this search, which has been implemented in the program AMoRE.

Introduction

Minimization of nondeterministic finite automata (”NFA”) is more difficult than that of deterministic finite automata. The problem is PSPACE-complete (except for the case of one-letter-alphabets) [6], whereas deterministic finite automata can be minimized in time O(n · log n) [4]. Moreover, there is in general not a unique minimal NFA recognizing a given regular language. Procedures for minimization of nondeterministic finite automata are investigated in several papers, e.g. Kameda and Weiner [10] (see also Indermark [7]) and Kim [11]. Further references are given in Brauer’s monograph [2]. The purpose of this note is twofold. First, we describe a general technique of constructing minimal NFA which is implicit in older papers like [10] and has been suggested in a different version in a recent contribution of Arnold, Dicky and Nivat [1]. The idea is to construct a nondeterministic “canonical automaton” in which any NFA recognizing the considered language occurs (via a homorphism) as a subautomaton. This means that the construction of the minimal NFA can be done in two steps: construction of the canonical automaton and search for a minimal subautomaton therein which accepts the same language. We compare two versions of “canonical automata” and develop a method of computing one of these versions (called “fundamental automaton”). The second issue is the search of a minimal NFA within a given (canonical) automaton. We outline a heuristic which improves the one of [11]. It yields an algorithm with worst-case-behaviour time O(2^{(n^{2})}), where n is the number of states of the minimal deterministic automaton of the considered language. The algorithm is practical in the sense that in many non-trivial examples the actual implementation works in acceptable time. However, we show that the heuristic fails in some cases to produce a minimal NFA. (This is true for both considered versions of canonical NFA.) It is open how to sharpen the heuristic in order to get an algorithm which always outputs a proper minimal NFA and is as “practical” as our heuristic. In the first section basics and terminology on finite automata are recalled (powerset construction, minimization of deterministic finite automata). In the second section we construct the “fundamental automaton” F of a regular language L and show that a minimal NFA accepting L can be found as a subautomaton of F. Then we give the announced sufficient (but not necessary) criterion for subautomata of F that accept L; the heuristic is then simply to find a subautomaton of F that satisfies this criterion and has a minimal number of states. Section 3 offers one of the rare examples where this heuristic fails to yield a minimal automaton. Section 4 outlines an implementation for the described strategy. In the last section, we give a different definition for the fundamental automaton in order to compare it to the “canonical automaton” as introduced in [1] (which contains as well any minimal NFA as subautomaton). We show that the fundamental and the canonical automaton may be different, and transfer the criterion mentioned above to the canonical automaton. An implementation (written in C) of the heuristic, based on the fundamental automaton, is part of the AMoRE program (computing Automata, MOnoids, and Regular Expressions), which is available via FTP (ftp.informatik.uni-kiel.de:pub/kiel/amore). We thank Wolfgang Thomas for helpful comments on previous versions of the paper.

1 Preliminaries

We use the standard notation of set theory and formal language theory. For a set P of sets we write ⋂ P for ⋂_{p∈P} p. We denote by |Q| the number of elements of Q. ∅ is the empty set and 2^{Q} is the set of all subsets of Q. ^{•} ⋃ denotes a union of disjoint sets. By Σ we indicate a finite alphabet, by a, b, c, … letters and by u, v, … words. The empty word is written ϵ. A nondeterministic finite automaton (NFA) is of the form A = (Q, Σ, I, δ, F) with a finite non-empty set of states Q, a finite non-empty alphabet Σ, a non-empty set of initial states I ⊆ Q, a transition function δ : Q × Σ ⟶ 2^{Q} and a set of final states F ⊆ Q. If |I| = 1 and ∀q ∈ Q ∀a ∈ Σ |δ(q, a)| = 1, then A is a deterministic finite automaton (DFA). A triple (q, a, q′) ∈ Q × Σ × Q with q′ ∈ δ(q, a) is called a transition. The transition function δ : Q × Σ ⟶ 2^{Q} can be extended in a natural way to a function from 2^{Q} × Σ^{∗} to 2^{Q}, usually also denoted by δ. We write p →_{A}^{w} q to indicate

that q ∈ δ(p, w) and say that there exists a path from p to q labelled w. If the components of an NFA A are not listed explicitly, we will denote by Q_{A}, I_{A}, F_{A} and δ_{A} its set of states (initial states, final states resp.) and its transition function. We will drop the subscripts only if the NFA is clear from the context. A word u ∈ Σ^{∗} is accepted by A, if δ(I, u) ∩ F ≠ ∅. The language accepted by A is L(A) = { u ∈ Σ^{∗} | δ(I, u) ∩ F ≠ ∅ }. Two NFA A and B are called equivalent if L(A) = L(B). An NFA A is called minimal if all NFA that are equivalent to A have at least as many states as A. We assign two languages to every state of an NFA.

Definition 1.1 ([10],[5]) Let A be an NFA and q ∈ Q. Then the pre-language of q and the post-language of q are given by pre(A, q) = L((Q_{A}, Σ, I_{A}, δ_{A}, {q})) and by post(A, q) = L((Q_{A}, Σ, {q}, δ_{A}, F_{A})), respectively. q is reachable if pre(A, q) ≠ ∅ and q is productive if q is reachable and post(A, q) ≠ ∅. Two states p, q ∈ Q are equivalent, written p ∼ q, if post(A, p) = post(A, q). [q] = { p | p ∼ q } denotes the equivalence class to which q belongs.

In [1], pre- and post-language are called history and prophecy. In the sequel all NFA have productive states only. Now we introduce three classical operations on automata and analyze pre- and postlanguages of the resulting automata.

Definition 1.2 ([10]) Let A be an NFA. Its reversed NFA is \overline{A} = (Q, Σ, F, \overline{δ}, I) with ∀a ∈ Σ ∀p, q ∈ Q : p ∈ \overline{δ}(q, a) ⟺ q ∈ δ(p, a). Given a word u = a_{1} … a_{n} the word \overline{u} = a_{n} … a_{1} is its reversed word. Given a language L the language \overline{L} = \{ \overline{u} | u ∈ L \} is its reversed language.

Obviously L(\overline{A}) = ⋃_{q∈F} post(\overline{A}, q) = \overline{⋃_{q∈F} pre(A, q)} = \overline{L(A)} for all NFA A. Furthermore A is a minimal NFA accepting L iff \overline{A} is a minimal NFA accepting \overline{L}. The next operation is the wellknown powerset construction.

Definition 1.3 ([12]) Let A be an NFA. The subset automaton for A, denoted D(A), is the DFA B = (Q_{B}, Σ, I_{B}, δ_{B}, F_{B}), where Q_{B} = { δ_{A}(I_{A}, u) | u ∈ Σ^{∗} } ⊆ 2^{Q}, I_{B} = { I_{A} }, F_{B} = { P ∈ Q_{B} | P ∩ F_{A} ≠ ∅ } and with δ_{B}(P, a) = δ_{A}(P, a) for all P ∈ Q_{B} and for all a ∈ Σ.

Obviously L(A) = ⋃_{q∈I} post(A, q) = post(B, I_{B}) = L(D(A)). Next we give the constructive definition of the minimal DFA for a given NFA.

Definition and Theorem 1.4 ([5],[10]) Let A be an NFA and B = D(A). The minimal DFA D = (Q_{D}, Σ, I_{D}, δ_{D}, F_{D}) for A, denoted M(B) or MD(A), can be constructed the following way: Q_{D} = {[ P ]|P ∈ Q_{B}}, I_{D} = [I_{B}], F_{D} = {[ P ]|P ∈ F_{B}} and for all states P of Q_{B} and for all a ∈ Σ, δ_{D}([P], a) = [δ_{B}(P, a)]. Let q be a state of A and [P] be a state of MD(A). We write q < [P] as an abbreviation for: ∃P′ ∈ [P] q ∈ P′. We give some relations that hold between postand pre-languages in A and D.

q ∈ F ∧ q < [P] ⇒ [P] ∈ F_{D} (1)

(2) q ∈ I ⇒ q < [P] where [P] is the initial state of D

p →_{A}^{a} q ∧ p < [P] ⇒ q < δ_{D}([P], a) (3)

Remark 1.5 For every regular language L, there is a unique (up to isomorphsm) minimal DFA D with L(D) = L, which we call “the” minimal DFA for a language L. The analogue is not true for minimal NFA since there are regular languages for which several non-isomorphic minimal NFA accepting these languages exist. All states of a minimal DFA are reachable and at most one state can be nonproductive. If it exists, this state is called the sink state or — because its postlanguage is the empty set — the empty state. Pre-languages of different states of a DFA are disjoint and post-languages of different states in a minimal DFA are different. The minimal DFA MD(A) for an NFA A with n states can have up to 2^{n} states.

The next theorem is interesting because it offers a way to compute the minimal DFA for a given language without computing the equivalence classes of states (as it is suggested by 1.4).

Theorem 1.6 (Brzozowski [3]) Let L be a regular language and D an arbitrary DFA accepting L. Then E := D(\overline{D}) is the minimal DFA accepting \overline{L}.

Definition 1.7 Let A = (Q, Σ, I, δ, F) and B be nondeterministic automata. A mapping h : Q → Q_{B} is called a morphism if h(I) ⊆ I_{B}, h(F) ⊆ F_{B} and h(δ(q, a)) ⊆ δ_{B}(h(q), a) for all q ∈ Q and a ∈ Σ. A is called a subautomaton of B if Q ⊆ Q_{B}, F = F_{B} ∩ Q, I = I_{B} ∩ Q and δ(q, a) ⊆ δ_{B}(q, a) ∩ Q for all q ∈ Q and a ∈ Σ. If δ(q, a) ⊆ δ_{B}(q, a) ∩ Q, we call A the subautomaton of B induced by Q. If h is a morphism from A to B then we denote by h(A) the subautomaton of B induced by the set h(Q) of states.

Remark 1.8 Let A and B nondeterministic automata and h a morphism from A to B. Then L(A) ⊆ L(h(A)) ⊆ L(B).

Proof We have p →_{A}^{w} q ⇒ h(p) →_{h(A)}^{w} h(q) ⇒ h(p) →_{B}^{w} h(q) and p ∈ F (I) ⇒

h(p) ∈ F_{B} (I_{B}). Thus an accepting path in A is mapped to an accepting path in h(A) which is an accepting path of B by definition. □

2 The Fundamental Automaton

In this section we construct for every regular language L an NFA F, called the fundamental automaton of L, such that for every NFA A accepting L there exists a morphism from A in F. We will use this fact to show that a minimal automaton accepting L can be found as a subautomaton of F. In order to simplify the notation we fix the language L. Let A = (Q, Σ, I, δ, F) be an arbitrary NFA accepting L, D = (Q_{D}, Σ, I_{D}, δ_{D}, F_{D}) the minimal DFA accepting L and E = (Q_{E}, Σ, I_{E}, δ_{E}, F_{E}) = D(\overline{D}). (Because of 1.6, E is the minimal DFA accepting L.) If E has a sink state then this state is not productive in the reversed automaton \overline{E} = (Q\overline{E}, Σ, I\overline{E}, δ\overline{E}, F\overline{E}) and we assume that this state and all transitions from this state are deleted in \overline{E}. \overline{E} has several important properties described in the following remark.

Remark 2.1 \overline{E} is a reversed automaton to a deterministic finite automaton. Therefore there exists for all words in L a unique accepting path in \overline{E}, and deletion of any transition in δ\overline{E} yields an automaton which accepts a proper subset of L. Moreover, a post-language of an arbitrary NFA accepting L is a subset of a disjoint union of post-languages of \overline{E}. E is isomorphic to MD(\overline{A}) and thus we can associate to every state r of E an equivalence class of sets of states of A (cf. Definition 1.4). For every state q of A we denote by q^{•} the set of states r of E with q < r.

Now we arrive at the definition of the fundamental automaton, given E = D(\overline{D}).

Definition 2.2 (The Fundamental Automaton) The fundamental automaton F = (Q_{F}, Σ, I_{F}, δ_{F}, F_{F}) is defined as follows:

Q_{F} = \{ P ⊆ Q\overline{E} | ⋂ P ≠ ∅\}
I_{F} = \{ P ∈ Q_{F} | P ⊆ I\overline{E} \}
F_{F} = \{ P ∈ Q_{F} | P ∩ F\overline{E} ≠ ∅ \}
δ_{F}(P, a) = \{ P′ ∈ Q_{F} | P′ ⊆ δ\overline{E}(P, a) \} for all P in Q_{F} and a in Σ.

We proceed in three steps. First, we show that the fundamental automaton accepts L. Then we verify that for each automaton A accepting L there exists a morphism from A into the fundamental automaton of L. This proves that a minimal automaton accepting L can be found as a subautomaton of F. We conclude with a condition that describes how to find certain subautomata of F that accept L.

Lemma 2.3 The fundamental automaton F is equivalent to \overline{E}.

Proof L(F) ⊇ L(\overline{E}) because \overline{E} is a subautomaton of F (take all subsets of Q_{F} of size 1). The following fact on the transiton function of F can be shown easily by an induction on the length of words w:

∀P, P′ ∈ Q_{F} ∀w ∈ Σ^{∗} P →_{F}^{w} P′ ⇒ ∀p′ ∈ P′ ∃p ∈ P p →_{\overline{E}}^{w} p′ (4)

Then the definition of initial and final states of F yields: if P →_{F}^{w} P′ is an accepting

path in F then there exists a state p′ ∈ P′ ∩ F\overline{E} and a state p ∈ P ⊆ I\overline{E} with p →_{\overline{E}}^{w} p′.

Thus L(F) ⊆ L(\overline{E}). □

Lemma 2.4 Let A be an NFA accepting L and F the fundamental automaton of L. The mapping q ↦ q^{•} is a morphism from A to F.

Proof

Because of Theorem 1.6, we may regard E as D(\overline{D(A)}). The states of E are thus sets of states of \overline{D(A)}. For a state q′ of \overline{D(A)}) and a state r of E, we have then q′ < r iff q′ ∈ r.

We will begin by showing that q ↦ q^{•} is a mapping from Q_{A} in Q_{F}.

Let q be a state of A and r ∈ q^{•}. Since all states of A are supposed to be productive, there is a state q′ of D(A) such that q ∈ q′. Since q < r and E is isomorphic to MD(\overline{A}), there is a state R of D(\overline{A}) such that q ∈ R and post(D(\overline{A}), R) = post(E, r). (Each state of E corresponds to a non-empty set of states of D(\overline{A}) whose elements have the same post-language.)

Now we have

post(\overline{D(A)}, q′) = pre(D(A), q′) ⊆ pre(A, q) = post(\overline{A}, q) ⊆ ⋃_{p∈R} post(\overline{A}, p) = post(D(\overline{A}), R) = post(E, r) = post(D(\overline{D(A)}), r) = ⋃_{p′∈r} post(\overline{D(A)}, p′)

Since different pre-languages of a DFA are disjoint, so are different post-language of \overline{D(A)}. Thus we may conclude that q′ ∈ r, i.e. r ∈ q^{•}′. Since r was chosen arbitrarily from q^{•}, we have shown q^{•} ⊆ q^{•}′.

We have q^{•}′ = {r ∈ Q_{E} | q′ ∈ r}, thus q′ ∈ ⋂ q^{•}′ ⊆ ⋂ q^{•}, showing that q^{•} is a state of F. So we have shown that q ↦ q^{•} is a mapping into F.

To show that it is a morphism, we have to verify q ∈ F (I) ⇒ q^{•} ∈ F_{F} (I_{F}) and

p →_{A}^{a} q ⇒ p^{•} →_{F}^{a} q^{•}.

q ∈ I_{A} q ∈ F_{A}  p →_{A}^{a} q
⇓  Definition of the reversed automaton
q ∈ F\overline{A} q ∈ I\overline{A}  q →_{\overline{A}}^{a} p
⇓  Equations (1,2,3)
q^{•} ⊆ F_{E} q^{•} ∩ I_{E} ≠ ∅ p^{•} ⊇ δ_{E}(q^{•}, a)
⇓  Definition of the reversed automaton
q^{•} ⊆ I\overline{E} q^{•} ∩ F\overline{E} ≠ ∅ q^{•} ⊆ δ\overline{E}(p^{•}, a)
⇓  Definition of the fundamental automaton
q^{•} ∈ I_{F}  q^{•} ∈ F_{F}  p^{•} →_{F}^{a} q^{•}
□

Theorem 2.5 A minimal automaton accepting L can be found as a subautomaton of F.

Proof Let A be a minimal NFA accepting L and let h : q ↦ q^{•} be the morphism of Lemma 2.4. The number of states of h(A) is less or equal to the number of states of A. Furthermore we have: L = L(A) ⊆ L(h(A)) ⊆ L(F) = L. Thus L(h(A)) = L and h(A) is a minimal NFA accepting L and a subautomaton of F. □

With the next lemma we give a criterion for equivalent subautomata of F that improves the one given by Kim [11] and was suggested by Kahlert [9]. Kim claimed that his criterion was necessary, which is not true in general. We start with an auxiliary definition. Let Q be a set, P ⊆ 2^{Q} and R ⊂ Q. We say P covers R with subsets iff R = ⋃{P ∈ P | P ⊆ R}.

Lemma 2.6 Let F_{P} be a subautomaton of F induced by the set P ⊆ Q_{F} of states. Assume

(i) P covers I\overline{E} with subsets and

(ii) P covers δ\overline{E}(P, a) with subsets for all P ∈ P, a ∈ Σ.

Then F_{P} is equivalent to F.

Proof Let P fulfill conditions (i) and (ii) and let p_{0} →_{\overline{E}}^{a_{1}} … →_{\overline{E}}^{a_{n}} p_{n} be an accepting

path in \overline{E}. We show that there exists an accepting path P_{0} →_{F_{P}}^{a_{1}} … →_{F_{P}}^{a_{n}} P_{n} in F_{P} with

p_{i} ∈ P_{i}. By p_{0} ∈ I\overline{E} and condition (i) there is a set P_{0} ∈ P with P_{0} ⊆ I\overline{E} and p_{0} ∈ P_{0}. Furthermore P_{0} is initial in F_{P}. We find P_{1} … P_{n} by induction in the following way: if p_{i} ∈ P_{i} then p_{i+1} ∈ δ\overline{E}(P_{i}, a_{i+1}); by condition (ii) there exists P_{i+1} ⊆ δ\overline{E}(P_{i}, a_{i+1}), P_{i+1} ∈ P with p_{i+1} ∈ P_{i+1}. By definition of F we get P_{i} →_{F}^{a_{i+1}} P_{i+1}. P_{n} is final in F

because p_{n} ∈ P_{n} and p_{n} is final in \overline{E}. Thus L(\overline{E}) ⊆ L(F_{P}). □

3 An Example

In this section we present a simple example that shows that the criterion given in 2.6 is not necessary for subautomata of the fundamental automaton which are equivalent to the given NFA. Thus it does not yield an algorithm for determining a minimal NFA in general. Consider the NFA A and its reversed NFA \overline{A} given by the following transition tables. Initial and final states are marked with “i” or “f”, respectively.

A  \begin{aligned}& a & b \\ f0 & 0, 2 \\ 1 & 3 & 2, 3 \\ i2 & 1 & 0, 1 \\ 3 & 3 & 1 \end{aligned}  \overline{A}  \begin{aligned}& a & b \\ i0 & 0 & 2 \\ 1 & 2 & 2, 3 \\ f2 & 0 & 1 \\ 3 & 1, 3 & 1 \end{aligned}

The following tables show the minimal DFA E equivalent to \overline{A}, the reverse of this DFA and the mapping q ↦ q^{•} from Q_{A} into 2^{Q_{E}}. The leftmost column of the first table contains for each state of E the corresponding states of \overline{A}.

\begin{aligned}& & a & b \\ \{0\} & ie_{0} & e_{0} & e_{1} \\ \{2\} & fe_{1} & e_{0} & e_{2} \\ \{1\} & e_{2} & e_{1} & e_{3} \\ \{2, 3\} & fe_{3} & e_{4} & e_{2} \\ \{0, 1, 3\} & e_{4} & e_{5} & e_{5} \\ \{0, 1, 2, 3\}, \{1, 2, 3\} & fe_{5} & e_{5} & e_{5} \end{aligned}  \begin{aligned}& a & b \\ fe_{0} & e_{0}, e_{1} \\ ie_{1} & e_{2} & e_{0} \\ e_{2} & & e_{1}, e_{3} \\ ie_{3} & & e_{2} \\ e_{4} & e_{3} \\ ie_{5} & e_{4}, e_{5} & e_{4}, e_{5} \end{aligned}  \begin{matrix}h(0) = & \{e_{0}, e_{4}, e_{5}\} \\ h(1) = & \{e_{2}, e_{4}, e_{5}\} \\ h(2) = & \{e_{1}, e_{3}, e_{5}\} \\ h(3) = & \{e_{3}, e_{4}, e_{5}\} \end{matrix}

The states of the fundamental automaton are certain subsets of Q_{E}. In fact, a look at the correspondence between E and D(\overline{D(A)}), which is not presented here, would show that the fundamental automaton contains actually all subsets of Q_{E}. That is why we do not present it here. But we show the transitition table of the image of A under the morphism h.

a  b
f{e_{0}, e_{4}, e_{5}} {e_{0}, e_{1}, e_{3}, e_{4}, e_{5}}  {e_{4}, e_{5}}
{e_{2}, e_{4}, e_{5}}  {e_{3}, e_{4}, e_{5}}  {e_{1}, e_{3}, e_{4}, e_{5}}
i{e_{1}, e_{3}, e_{5}}  {e_{2}, e_{4}, e_{5}}  {e_{0}, e_{2}, e_{4}, e_{5}}
{e_{3}, e_{4}, e_{5}}  {e_{3}, e_{4}, e_{5}}  {e_{2}, e_{4}, e_{5}}

This transition table has to be interpreted like this: if Q ⊆ Q_{E} is in the line corresponding to P ⊆ Q_{E} and letter a, then in the fundamental automaton there is a transition from P with a to each subset of Q. So the subautomaton of the fundamental automaton induced by the image of h is:

a  b
fh(0) h(0), h(2), h(3)
h(1)  h(3)  h(2), h(3)
ih(2)  h(1)  h(0), h(1)
h(3)  h(3)  h(1)

The automaton is (up to isomorphism) the same as A, except for one superflous transition. The chosen set of states P = {h(0), h(1), h(2), h(3)} of the fundamental automaton covers indeed the set of initial states of \overline{E} with subsets, so the first criterion of 2.6 holds. But the transition table shows that the set δ\overline{E}(\{e_{0}, e_{4}, e_{5}\}, b) = \{e_{4}, e_{5}\} is not covered with subsets; so the second property does not hold. Thus h(A) is a subautomaton of the fundamental automaton that accepts L, but does not fulfill the conditions (i) and (ii) of Lemma 2.6. In fact, there is no set of states with the property of Lemma 2.6 that has less than 5 states, so for this example language the suggested heuristic fails to find a minimal NFA.

4 Some Comments on the Practical Computation

In this section we outline an algorithm to compute a small NFA. This algorithm is based on the results of Section 2. An implementation of this strategy (with some improvements not described here) is part of the AMoRE-System, available via Anonymous FTP.

Main Idea

The main idea how to compute a small NFA for a given regular language L is to proceed in four steps:

1. Compute a minimal DFA E for \overline{L}.

2. Determine the allowed sets, i.e. those subsets of the state set of E that are states of the fundamental automaton.

3. Search for a selection P of allowed sets that satisfies the cover/closure property (i), (ii) of Lemma 2.6 and is minimal with that property.

4. Compute the subautomaton of the fundamental automaton induced by the selection P.

The most important point is, of course, the step 3. For this step we will give (in Figure 1) a recursive procedure cover that explores in a backtracking strategy all reasonable extensions of a given selection to a selection satisfying the cover/closure property. cover receives three arguments called allowed, selected, remain for subsets of Q_{E}. The intuitive meaning is the following: allowed contains all allowed sets that must be considered for possible extensions of the set selected. selected contains the subsets of Q_{E}-states that have been selected so far. remain contains all subsets of Q_{E}-states for which we will have to make sure (possibly by further selections) that selection covers them by subsets. More precisely, the pre- and postcondition of cover are given by:

Precondition: I\overline{E} ∉ remain ⇒ (selected covers I\overline{E} by subsets) and ∀R ∈ selected ∀a ∈ Σ : δ\overline{E}(R, a) ∉ remain ⇒ (selected covers δ\overline{E}(R, a) by subsets) Postcondition: If there is a P ⊇ selected with P\selected ⊆ allowed such that P fulfills the cover/closure property of Lemma 2.6, then the global variable best solution contains such a P of minimal size, otherwise best solution remains

unchanged. In any case, best known = |best solution|.

With this procedure cover, the algorithm for the computation of a small NFA looks like this:

1. Compute the minimal DFA D for L.

2. Apply the powerset constuction to \overline{D} and obtain E.

3. Let best known = |Q_{E}| + 1.

4. cover(\{P ⊆ Q_{E} | ⋂ P ≠ ∅\}, ∅, \{I\overline{E}\})

5. Define the output automaton A = (Q, Σ, I, δ, F) by

         Q = best solution,

I = \{P ∈ Q | P ⊆ I\overline{E}\}, F = \{P ∈ Q | P ∩ F\overline{E} ≠ ∅\}, δ(R, a) = \{P ∈ Q | P ⊆ δ\overline{E}(R, a)\} for all R ∈ Q, a ∈ Σ.

cover(allowed,selected,remain)

/* allowed, selected, remain ⊆ Q_{E} fulfill the precondition */ /* explores all reasonable extensions of selected to a set satisfying the cover/closure property of Lemma 2.6 */ if remain = ∅ then

/* no sets remain to be covered, we have a solution! */

     best solution := selected

else /* there are still sets that remain to be covered */

     for all current ∈ remain do

if selected covers current with subsets then /* current is already covered, treat the rest of remain */

          cover(allowed, selected, remain\{current} )

else /* current has to be covered by further selections */

          if |selected| + 1 < best known

/* stop backtracking if best known solution cannot be improved */ for all P ⊆ current with P ∈ allowed do

               allowed := allowed\{P }
               cover(allowed, selected ∪ \{P \}, remain ∪ \{δ\overline{E}(P, a) | a ∈ Σ\})

rof fi

fi rof

fi

Figure 1: The recursive procedure cover

One important and simple way to improve this strategy is to compare the size of the state set of E and D after line 2 and exchange them if D is smaller. In this case, the algorithm computes a small NFA for the reversed language \overline{L}, thus the output NFA has to be reversed as well. Note that the modification of allowed in the last for-loop is to avoid that one and the same selection of subsets is explored more than once: When inside one incarnation of cover the addition of a certain set P to the current selection has been fully explored, it is not necesarry to consider P any more unless this incarnation is exited and the current selection becomes smaller. In the programm system AMoRE, a similar (but non-recursive) algorithm has been implemented. One great problem one has to deal with is how to represent the subsets of Q_{E} and 2^{Q_{E}} without wasting too much space. We chose to represent the subsets of Q_{E} by 32-bit integers, so the available implementation does not work if both the minimal DFA for L and for \overline{L} have more than 32 states. Another problem is how to realize the last for-loop running over all subsets of a given set. Here, we have decided to trace the sets in the canonical ordering they have when represented by integers. Experience shows that this order influences the performance of the algotithm very much, so it might be advantageous to choose a more sophisticated ordering: For example, one could try to treat the large subsets before the small ones or vice versa.

5 Fundamental vs. Canonical Automaton

In this section, we will give a more abstract definition of the fundamental automaton, which is, however, less suitable for actual calculation. Using this characterization, we compare the fundamental automaton to a different automaton, the so-called canonical automaton, defined by Arnold, Dicky and Nivat in [1]. This one has similar properties as the fundamental automaton, but it may be smaller. Moreover, we transfer the mentioned sufficient cover/closure property (conditions (i),(ii) of Lemma 2.6) for equivalent subautomata from the fundamental to this canonical automaton.

5.1 Fundamental Automaton Revisited

Define the MDFA D′ (minimal deterministic finite automaton) for a language L by

Q_{D′} = {w^{−1}L | w ∈ Σ^{∗}}
I_{D′} = {L}
δ_{D′}(w^{−1}L, a) = (wa)^{−1}L
F_{D′} = {w^{−1}L | ϵ ∈ w^{−1}L}

Observing the fact \overline{w}^{−1}\overline{L} = \overline{Lw^{−1}}, we get that the MDFA for \overline{L} is isomorphic to the following DFA E′ via the mapping M ↦ \overline{M}.

Q_{E′} = {Lw^{−1} | w ∈ Σ^{∗}}
I_{E′} = {L}
δ_{E′}(Lw^{−1}, a) = L(aw)^{−1}
F_{E′} = {Lw^{−1} | ϵ ∈ Lw^{−1}}

With this definition we can define the fundamental automaton F′ differently than in Section 2 by:

Q_{F′} = {P ⊆ Q_{E′} | ⋂ P ≠ ∅}
I_{F′} = {P ∈ Q_{F′} | ϵ ∈ ⋂ P }
δ_{F′}(P, a) = \{R ∈ Q_{F′} | R ⊆ δ\overline{E′}(P, a)\}
F_{F′} = {P ∈ Q_{F′} | L ∈ P }

To see that this definition is indeed equivalent to the one given before, let E = D(\overline{D′}) with D′ being the minimal DFA for the language L as described above, i.e. the states of D′ are left quotients. (Note that D′ is a possible choice for the D of the last section, so E is a possible choice for the E in SectionSecFunAut). Let F′ be the fundamental automaton as defined in Definition 2.2 of Section 2, i.e. with states in 2^{Q_{E}}.

Lemma 5.1 F′ is isomorphic to F.

Proof It is a well known fact that there exists an isomorphism α from E onto E′, namely

α : Q_{E} ⟶ Q_{E′} , ({u^{−1}L | uw ∈ L}) ↦ Lw^{−1}.

We claim that the extension from α to Q_{F} ⊆ 2^{Q_{E}} into 2^{Q_{E′}} is an isomorphism from Q_{F} onto Q_{F′}. We will denote this extension again by α. Since the original α is injective, so is this extension.

Let ∅ ≠ M ⊆ Q_{E} = {{u^{−1}L | uw ∈ L} | w ∈ Σ^{∗}}. Then we have the following equivalence showing that α is indeed a mapping from Q_{F} into Q_{F′}.

M ∈ Q_{F} ⟺ ⋂ M ≠ ∅
⟺ ∃u^{−1}L ∈ Q_{D′} : ∀P ∈ M : u^{−1}L ∈ P
⟺ ∃u ∈ Σ^{∗} : u^{−1}L ≠ ∅ ∧ ∀Lw^{−1} ∈ α(M) : uw ∈ L
⟺ ⋂ α(M) ≠ ∅
⟺ α(M) ∈ Q_{F′}

Similarly, we have

M ∈ I_{F} ⟺ M ⊆ I\overline{E} = F_{E}
⟺ ∀P ∈ M : P ∩ I_{D′} ≠ ∅
⟺ ∀P ∈ M : L ∈ P
⟺ ∀Lw^{−1} ∈ α(M) : w ∈ L
⟺ ϵ ∈ ⋂ α(M)
⟺ α(M) ∈ I_{F′}

The correspondence of the set of final states is shown by the following equivalences:

M ∈ F_{F} ⟺ ∅ ≠ M ∩ F\overline{E} = M ∩ I_{E}
⟺ I\overline{D′} ∈ M
⟺ {u^{−1}L ∈ Q_{D} | ϵ ∈ u^{−1}L} ∈ M
⟺ L = α({u^{−1}L | ϵ ∈ u^{−1}L}) ∈ α(M)
⟺ α(M) ∈ F_{F′}

Finally, we check that α commutes with the transition relations. This is verified as follows:

N ∈ δ_{F}(M, a) ⟺ N ⊆ δ\overline{E}(M, a)
⟺ α(N) ⊆ α(δ\overline{E}(M, a))
⟺ α(N) ⊆ δ\overline{E′}(α(M), a)
⟺ α(N) ∈ δ_{F′}(α(N), a)

This completes the proof and establishes the claimed correspondence of the two definitions for the fundamental NFA. In the remainder of the paper we will write F instead of F′. □

5.2 The Canonical Automaton

We compare the fundamental automaton to a different NFA introduced by Arnold, Dicky and Nivat in [1]. They defined the canonical automaton C as described now. We start with an auxiliary definition. For K ⊆ Σ^{∗}, let ϕ(K) = {u ∈ Σ | uK ⊆ L} = ⋂_{v∈K} Lv^{−1}.

Definition 5.2 The canonical automaton C is given by

Q_{C}= {ϕ(K) | K ⊆ Σ^{∗} and K, ϕ(K) ≠ ∅} = {⋂ P ≠ ∅ | P is a nonempty set of right quotients of L}

I_{C} = {⋂ P ∈ Q_{C} | ϵ ∈ ⋂ P }

δ_{C}(⋂ P, a) = {⋂ R ∈ Q_{C} | (⋂ P)a ⊆ ⋂ R} for all ⋂ P ∈ Q_{C} and all a ∈ Σ^{∗} :

F_{C} = {⋂ P ∈ Q_{C} | ⋂ P ⊆ L}

The canonical and the fundamental automaton have similar properties. For example, it is shown in [1] that for any NFA A accepting L, there exists a morphism from A into C, namely q ↦ ϕ(post(A, q)). Thus any minimal NFA accepting L is isomorphic to some subautomaton of C. An interesting fact about the canonical automaton is that it is in some sense the smallest NFA with that property, because any epimorphism from C onto an equivalent NFA is injective. Let us denote by F the fundamental automaton as defined in this section. The relation between the fundamental automaton and the canonical automaton is illustrated by the observation of [1] that a morphism f from F into C is given by

f : P ↦ ϕ(post(F, P)) = ⋂ P

To see the last equality we observe that for any w ∈ Σ^{∗} and any P ∈ Q_{F} we have

w ∈ post(F, P) ⟺ ∃R ∈ Q_{F} : R ∈ F_{F} ∧ R ∈ δ_{F}(P, w)
⟺ ∃R ∈ Q_{F} : L ∈ R ∧ δ_{E}(R, \overline{w}) ⊆ P
⟺ ∃R ⊆ Q_{E} : ⋂ R ≠ ∅ ∧ L ∈ R ∧ ∀Lv^{−1} ∈ R(L(wv)^{−1} ∈ P)
⟺ Lw^{−1} ∈ P.

(To see the last implication from right to left choose R := {L}.) This shows for any u ∈ Σ^{∗} and any P ∈ Q_{F}

u ∈ ϕ(post(F, P)) ⟺ ∀w ∈ post(F, P) : uw ∈ L
⟺ ∀w ∈ Σ^{∗} : Lw^{−1} ∈ P ⇒ uw ∈ L
⟺ ∀w ∈ Σ^{∗} : Lw^{−1} ∈ P ⇒ u ∈ Lw^{−1}
⟺ u ∈ ⋂ P

The morphism f is always surjective, and it is injective if there is no right quotient that is a superset of a nonempty intersection of other right quotients. There are examples where there is such a right quotient. For example for L = {aa, ab, bb}, the automaton F has 5 states (namely {La^{−1}}, {Lb^{−1}}, {La^{−1}, Lb^{−1}}, {L} and {{ϵ}}), whereas C has 4 states (namely {a}, {a, b}, L and {ϵ}); so the two automata F and C are in general not isomorphic. The conditions of Lemma 2.6 leading to the minimization heuristic can be transfered to C, yielding another heuristic for finding a small NFA for a given language.

5.3 A Criterion for Equivalent Subautomata of the Canonical NFA

Lemma 5.3 Let P ⊆ Q_{F} and P_{∩} ⊆ Q_{C} with P = {P ⊆ Q_{E} | ⋂ P ∈ P_{∩}}. (That is, P = f^{−1}(P_{∩}), with f being the morphism P ↦ ⋂ P from above.) Let the following two properties be fulfilled:

(i) P covers I\overline{E} with subsets and

(ii) For all R ∈ P and for all a ∈ Σ, P covers δ\overline{E}(R, a) with subsets.

We claim that the subautomaton C_{P_{∩}} of C induced by P_{∩} recognizes L.

Proof The direct proof of this result is possible, but we can argue simply like this: Because of Lemma 2.6, the subautomaton F_{P} of F induced by P is equivalent to A. The subautomaton C_{P_{∩}} is simply the image of F_{P} under the morphism P ↦ ⋂ P, so we have L ⊆ L(C_{P_{∩}}) ⊆ L(C) = L, showing our claim. □

Unfortunately, this cover/closure property of Lemma 5.3 is not necessary for equivalent subautomata of C, so also for C it does not give a heuristic that always produces a minimal NFA. One way of making use of this lemma would be to proceed as described in Secion 4, but put together states that have the same image under P ↦ ϕ(post(F, P) before the backtracking is started.

6 Conclusion

The minimization of nondeterministic finite automata is a difficult problem. One possible approach is to search among the subautomata of either the fundamental or the canonical automaton of a language. Both of these do contain all minimal NFA as subautomata, but we have no efficiently testable criterion that characterizes those subautomata that accept the same language. All we have is a sufficient criterion, so one can at least search for subautomata fulfilling this. It remains an open question if and how this criterion can be modified so that it characterizes all equivalent subautomata of the fundamental or the canonical automaton. If this modification is not possible, it would be interesting at least to know for which languages the mentioned sufficient criterion will be necessary. Apart from the minimization problem the definition and the properties of the fundamental and canonical automaton are interesting. Both of these are unique for a given regular language. Both contain homomorphic images of all automata equivalent to themselves, and the canonical automaton is in some sense the smallest with that property.

References

[1] A. Arnold, A. Dicky, M. Nivat, A note about minimal non-deterministic automata; in: Bulletin of the EATCS 47, June 1992, pp. 166-169.

[2] W. Brauer, Automatentheorie, Teubner, Stuttgart 1984.

[3] J.A. Brzozowski: Canonical regular expressions and minimal state graphs for definite events, in: Proc. Symp. on Math. Theory of Automata, Vol. 12, Brooklyn, N. Y.: Brooklyn Polytechnic Institute, 1963, pp. 529 -561.

[4] J.E. Hopcroft: An n log(n) algorithm for minimizing states in a finite automaton; in: Z. Kohavi, A. Paz (Eds.): Theory of Machines and Computation; Academic Press, New York etc., 1971, pp. 189-196.

[5] J.E. Hopcroft, J.D. Ullman: Introduction to Automata Theory, Languages, and Computation; Addison-Wesley, 1979.

[6] M.R. Garey, D.S. Johnson: Computers and Intractability – A Guide to the Theory of NP-Completeness; Freeman, San Francisco, 1979.

[7] K. Indermark: Zur Zustandsminimisierung nichtdeterministischer erkennender Automaten; GMD Seminarberichte Bd. 33, Gesellschaft für Mathematik und Datenverarbeitung, St. Augustin – Bonn, 1970.

[8] T. Jiang, B. Ravikumar: Minimal NFA Problems Are hard (Extended Abstract); in: J.Leach Albert, B. Monien, M.Rodriguez Artalejo (Eds.): Automata, Languages and Programming, 18th International Colloquium, Madrid, July 1991, Proceedings, LNCS 510, Springer, Berlin etc., 1991, pp. 629-640.

[9] T. Kahlert: Ein Verfahren für die Minimierung nichtdeterministischer endlicher Automaten und seine Implementierung; Diplomarbeit, Christian-Albrechts-Universität, Kiel, 1991.

[10] T. Kameda, P. Weiner: On the State Minimization of Nondeterministic Finite Automata; IEEE Trans. Comp. C–19(1970), pp. 617-627.

[11] J. Kim: State minimization of nondeterministic machines; IBM Thomas J. Watson Res. Center Rep. RC 4896, 1974.

[12] M.O. Rabin, D. Scott: Finite Automata and their decision problems; IBM J. Res. and Develop. 3, April 1959, pp. 114-125.