Closure properties

The question

We say that $\mathrm{Rat}$ is closed under an operation if applying it to regular languages always gives a regular language. By definition, $\mathrm{Rat}$ is closed under union, product and star. What about the other operations of chapters 1 and 2: transpose, prefixes, complement, intersection?

Thanks to Kleene's theorem, we have two tools to answer, and each time we choose the more convenient one:

• reasoning on expressions, by induction on their structure;
• reasoning on automata, by transforming them.

In both cases, the proof is constructive: it gives an algorithm that computes the expression or the automaton of the result.

Throughout the chapter, $L$, $L_1$ and $L_2$ are regular languages.

The transpose

$L^t$ contains the words of $L$ written backwards. Is it regular? Yes.

Using automata

We take an automaton for $L$, reverse the direction of all transitions, and swap the initial and final states. A successful path of the original automaton, read backwards, is a successful path of the new automaton, and its label is transposed.

The transpose of a DFA is in general not deterministic: several transitions with the same letter can arrive in the same state, and there are as many initial states as the original automaton had final ones.

Using expressions

We define $e^t$ by induction, following the six cases. Be careful: the naive version is wrong.

The naive column forgets to transpose the subexpressions: this is the typical mistake in a definition by induction, where the transformation is applied at the current level without being propagated. On $e = (ab)c$, it gives $c(ab)$, whereas the transpose of $abc$ is $cba$. The correct column gives $c^t (ab)^t = c\,(b^t a^t) = cba$.

The order in a union does not matter at all ($e^t + f^t \equiv f^t + e^t$); in a product, it is essential.

Prefixes, suffixes, factors

Prefixes

Is $\mathrm{Pref}(L)$ regular? Yes. A word $u$ is a prefix of a word of $L$ if there is a sequence $w$ such that $uw \in L$. On an automaton: $u$ leads from the initial state to a state $q$ from which a final state can still be reached, that is, a co-accessible state. Hence the construction: make all co-accessible states final.

State 3 is not co-accessible: if we made it final, we would accept $b$, which is a prefix of no word of $ab^*c$. We trim first, then make everything final.

$\mathrm{Pref}(ab^*c) = \varepsilon + ab^* + ab^*c$.

Suffixes

Is $\mathrm{Suff}(L)$ regular? Yes, by the symmetric construction: we make all accessible states initial. We can also reuse what we already know:

A suffix of $u$, written backwards, is a prefix of $u^t$.

Factors

Is $\mathrm{Fact}(L)$ regular? Yes: a factor is a prefix of a suffix,

On the trim automaton, this amounts to making all states both initial and final.

Subwords

Is the language of the subwords of the words of $L$ regular? Yes.

Using automata. A subword is obtained by erasing letters. So we double each transition $p \xrightarrow{a} q$ with a spontaneous transition $p \xrightarrow{\varepsilon} q$, which allows taking the transition without reading its letter.

(The loop $1 \xrightarrow{\varepsilon} 1$ is useless, so we do not draw it.)

Using expressions. We replace each letter $a$ with $a + \varepsilon$, and touch nothing else:

Thus $ab^*c$ becomes $(a + \varepsilon)(b + \varepsilon)^*(c + \varepsilon) \equiv (a + \varepsilon)b^*(c + \varepsilon)$.

Union, complement, intersection

Union

$L_1 \cup L_2$ is regular by definition: it is a regular operation. For automata, we put the two side by side (several initial states are allowed), or we apply Thompson's construction.

Complement

Is $\overline{L} = \Sigma^* \setminus L$ regular? Yes, but the proof requires some care.

The intuition is simple: an automaton is a machine that answers yes or no with a finite memory; for the complement, it is enough to give the opposite answer. Hence the idea: swap the final and non-final states. Let us see whether it works.

First attempt, on an NFA. This automaton recognises $a^+$:

After the swap:

It accepts $a$, by the path that stays in 0. But $a \in L$! In an NFA, a word is accepted if there is one successful path; its complement would require that no path succeeds. Swapping the final states turns “there is a path that ends in $F$” into “there is a path that ends outside $F$”, which is not the negation. We need a deterministic automaton, in which each word has only one path.

Second attempt, on a DFA. Over $\Sigma = \{a, b\}$, this automaton recognises $\{a\}$:

After the swap:

It accepts only $\varepsilon$. And $b$, which is not in $L$, is accepted by neither of the two automata: the machine gets stuck reading it, and getting stuck means rejection in both cases. We need a complete automaton, which never gets stuck.

Third attempt, on a complete DFA. We complete it with a sink, then swap:

This time, each word has exactly one path, which ends in a final state of one of the two automata and not of the other.

The cost is that of determinisation: up to $2^n$ states for an NFA with $n$ states.

Intersection

Is $L_1 \cap L_2$ regular? The question is far from obvious: intersection is not one of the regular operations.

A first answer, by De Morgan's laws:

Complement and union preserve $\mathrm{Rat}$: so does intersection. Yes. But as an algorithm, it is a disaster:

• the complement of each automaton requires determinising it: up to $2^n$ states;
• union, by Thompson, gives back a nondeterministic automaton;
• the final complement requires determinising again: up to $2^{2^n}$ states.

We need a direct construction.

The synchronised product

The idea

A word is in $L_1 \cap L_2$ if it is accepted by the automaton $A_1$ and by the automaton $A_2$. So we run both automata at the same time, on the same word: the state of the combined machine is a pair (state of $A_1$, state of $A_2$). Each letter moves both components forward.

As for determinisation, we build only the accessible pairs, starting from the initial pairs.

An example

$L_1$: the words with an even number of $a$ (the P / I automaton of chapter 3). $L_2$: the words that end with $b$.

The product has initial state $(P, 0)$, and single final state $(P, 1)$: even number of $a$, and last letter $b$.

What it costs, what it allows

The product has at most $n \times m$ states, against $2^{2^n}$ for De Morgan. It works just as well on NFAs as on DFAs, and the product of two DFAs is a DFA.

By changing only the final states, the same product gives other operations, provided both automata are complete (otherwise getting stuck in one also stops the other):

• union: the pairs of which at least one component is final, $(F_1 \times Q_2) \cup (Q_1 \times F_2)$;
• difference $L_1 \setminus L_2$: the pairs $(q_1, q_2)$ with $q_1 \in F_1$ and $q_2 \notin F_2$, if $A_2$ is deterministic.

Deciding

The synchronised product answers questions we could not settle until now.

Emptiness. $L(A) = \emptyset$ if and only if no final state is accessible. This is a graph traversal.

Inclusion. $L_1 \subseteq L_2$ if and only if $L_1 \cap \overline{L_2} = \emptyset$. We complement $A_2$ (determinise, complete, swap), take the product with $A_1$, and test emptiness.

Equivalence. $L_1 = L_2$ if and only if $L_1 \subseteq L_2$ and $L_2 \subseteq L_1$.

In chapter 2, we wondered how to know whether two regular expressions are equivalent. We now have an algorithm: compile both expressions into automata, and test equivalence. It always answers, yes or no. We say that the equivalence of regular expressions is decidable. Chapter 7 will give another method: comparing the minimal automata.