Lattices of languages

Mikołaj Bojańczyk

zajęcia / courses

Fix some alphabet $\Sigma$ . Define a profinite implication to be a pair of profinite words $(w,v)$ , which is written by $w \rightarrow v$ . We say that a regular language $L \subseteq \Sigma^*$ satisfies the implication if

$w \in \bar L \qquad \mbox{implies} \qquad v \in \bar L$

The following theorem, shows that profinite implications are exactly what is needed to characterize families of languages that are closed under union and intersection (and which contain the empty and full language).

Theorem. Let $\Sigma$ be an alphabet, and let $\Ll$ be a class of regular subsets of $\Sigma^*$ . The following conditions are equivalent:
a) $\Ll$ contains the empty and full languages, and is closed under union and intersection;
b) there is a set $I$ of profinite implications that defines $\Ll$ in the sense that a language belongs to $\Ll$ if and only if it satisfies all implications in $I$ .

Proof. Let us begin with the easier implication from b) to a). It is easy to see that the empty and full languages satisfy all profinite implications, and therefore they must belong to any set defined by profinite implications. It remains to show that if regular languages $L$ and $K$ satisfy all implications in a set $I$ , then the same holds for their union and intersection. This follows straight from the definition of satisfying implications and the following two observations:

$\begin{eqnarray*} \overline {L \cup K} = \overline L \cup \overline K\\ \overline {L \cap K} = \overline L \cap \overline K\end{eqnarray*}$

We are left with the implication from a) to b). Suppose that $\Ll$ contains the empty and full languages. Define $I$ to be the set of profinite implications that are satisfied by all regular languages in $\Ll$ . We claim that $I$ defines $\Ll$ . Clearly every language in $\Ll$ satisfies all implications in $I$ . It remains to show that if a regular language $L$ satisfies all implications in $I$ , then it belongs to $\Ll$ .

Lemma. For every profinite $w \in \bar L$ there is some $K_w \in \Ll$ such that

$w \in \bar K_w \subseteq \bar L.$

Proof. Let $v$ be a profinite word outside $\bar L$ . This means that $L$ violates the profinite implication $w \to v$ . Since $L$ satisfies all profinite implications in $I$ , it follows that the profinite implication $w \to v$ does not belong to $I$ , and therefore it is violated by some language in $\Ll$ , call it $K_{wv}$ . The language $K_{wv}$ , as a language violating $w \to v$ , is such that

$w \in \overline K_{wv} \qquad \mbox{and} \qquad v \not \in \overline K_{wv}$

It follows that the intersection

$\bigcap_{v \not \in \bar L} \overline K_{wv}$

is contained in $\bar L$ . By compactness, a finite subintersection is already included in $\bar L$ . Since $\Ll$ is closed under finite intersection, the proving the lemma. $\Box$

From the lemma it follows the sets $\bar K_w$ , ranging over $w\in \bar L$ , form a cover of the set $\bar L$ . Since $\bar L$ is clopen, there is a finite subcover, i.e.

$\overline L = \overline K_1 \cup \cdots \cup \overline K_n$

for some languages $K_1,\ldots,K_n \in \Ll$ . By since the closure operator distributes across union, and the family $\Ll$ is closed under finite union, it follows that $\overline L$ is equal to $\overline K$ for some $K \in \Ll$ . Finally, as we have shown here, the closure operator is a one-to-one correspondence between regular languages and clopen sets, and therefore $L=K$ . $\Box$

zajęcia / courses

Lattices of languages

Leave a Reply