Generators of families of langauges?

From Wikipedia's definition of regular langauges


The collection of regular languages over an alphabet $Σ$ is defined
recursively as follows:

• The empty language $Ø$ is a regular language.

• For each $a ∈ Σ$, the language $\{a\}$ is a regular language.

• If $A$ and $B$ are regular languages, then $A \cup B$ (union), $A • B$ (concatenation), and $A^*$ (Kleene star) are regular languages.

• No other languages over$ Σ$ are regular.

The regular languages also form a (full) AFL.

Parallel to the concept of generator for a sigma algebra, do the regular languages form the minimal (full) AFL (or (full) semi-AFL, full trio, trio, ...) that contains the empty language, and $\{a\}, a ∈ Σ$? In other words, are the minimal (full) AFL (or (full) semi-AFL, full trio, trio, ...) generated by the empty language, and $\{a\}, a ∈ Σ$ exactly the regular langauges?

For the sake of notation, let's call a family of languages $\mathcal{L}$ that contains

• the empty set $\emptyset$ and

• all singleton sets $\{a\}$, $a$ some symbol,

a founded family, and

$\qquad\displaystyle \mathcal{L}_+ = \{ L \in \mathcal{L} \mid \varepsilon \not\in L\}$.

Let $L \in \mathrm{REG}_+$ arbitrary. We will construct $L$ from only the empty and singleton sets using the trio operations

• $\varepsilon$-free homomorphism,

• inverse homomorphism and

• intersection with regular languages,

thus proving that (1) all founded trios also contain $\mathrm{REG}_+$. Furthermore, (2) $\mathrm{REG}_+$ it is a founded trio itself. Therefore, we have shown that $\mathrm{REG}_+$ is the minimal founded trio.

-
It suffices to show that $\Sigma^+ \supset L$ is contained in every founded trio $\mathcal{T}$; the rest is trivial by $L = \Sigma^+ \cap L \in \mathrm{REG}_+$.

We define for any alphabet $\Sigma$ a marked copy $\hat{\Sigma} = \{ \hat{a} \mid a \in \Sigma \}$ and two homomorphisms $h,g : \Sigma \cup \hat{\Sigma} \to \Sigma^*$ by

$\qquad\displaystyle
h(a) = \begin{cases}
a &, a \in \Sigma \\
\varepsilon &, a \in \hat{\Sigma}
\end{cases}
$

and

$\qquad\displaystyle
g(a) = \begin{cases}
b &, a = b \in \Sigma \\
b &, a = \hat{b} \in \hat{\Sigma}
\end{cases}
$.

Now consider

$\qquad\displaystyle L' = \Sigma \hat{\Sigma}^*$.

By noting that

• $\Sigma = h(L') \iff h^{-1}(\Sigma) = L'$,

• $g(L') = \Sigma^+$ and

• $g$ is $\varepsilon$-free,

we obtain from the trio closure properties that

$\qquad\displaystyle \Sigma \in \mathcal{T} \implies \Sigma^+ \in \mathcal{T}$.

But since $\Sigma$ is the pre-image of every $\{a\} \subseteq \Sigma$ with suitable constant homomorphism $h_a(b) = a$ we have $\Sigma \in \mathcal{T}$ by foundedness and closure under inverse homomorphism.

-
We check the conditions of a founded trio for $\mathrm{REG}_+$:

• Closure under $\varepsilon$-free homomorphism: clear since $\mathrm{REG}$ has this property and no such homomorphism can generate $\varepsilon$ from an $\varepsilon$-free language.

• Closure under inverse homomorphism: clear since $\mathrm{REG}$ has this property and the image of $\varepsilon$ is always $\varepsilon$.

• Closure against intersection with regular languages: clear by def.

• Foundedness: clear by def; all required sets are regular and don't contain the empty word..

$\mathrm{REG}$ actually is the minimal "founded" trio if you add $\{\varepsilon\}$ to the base; a similar proof goes through.

Furthermore, $\mathrm{REG}_+$ is not a full trio (cone) because of it's lack of empty words. We extend above proof by noting that containment of $\mathrm{REG}_+$ now implies containment of $\mathrm{REG}$ (any regular language $L$ is the image of $\hat{a}L \in \mathrm{REG}_+$ by a homomorphism that deletes only $\hat{a}$). Since $\mathrm{REG}$ is itself a cone it is also the minimal cone.

The properties extend to (semi-)AFLs, i.e. $\mathrm{REG}_+$ is the minimal (semi-)AFL and $\mathrm{REG}$ is the minimal full (semi-)AFL.

StackExchange Computer Science Q#26348, answer score: 6