Generators of families of langauges?

Question

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?

Answer 1

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

1. the empty set $\emptyset$ and
2. 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.

---

1. 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.

2. 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.