# Generators of families of 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?

• Quoting from Hopcroft/Ullman (not the subsequent Hopcroft/Motwani/Ullman, which omits the discussion), "... the regular sets are the smallest full trio. They are also a full AFL and therefore the smallest full AFL. The $\epsilon$-free regular sets are the smallest AFL, as well as the smallest trio." (But you probably already knew that.) – Rick Decker Jun 3 '14 at 1:01
• Thanks, @Rick. I didn't. What about context free langauges, context-sensitive langauges, recursive langauges, and recursively enumerable langauges? – Tim Jun 3 '14 at 1:08
• Continuing, H/U state that CFL's are full AFL's as are r.e languages. The CSL's are an AFL, but not a full AFL. In my annotations to my copy of H/U, I have that recursive languages are trios, but nothing else (though my marginalia didn't include a proof and it's been years since I looked at this stuff).. – Rick Decker Jun 3 '14 at 1:30
• @RickDecker: Ha, had I read that before starting to compose my answer, I could have saved me some trouble! – Raphael Jun 3 '14 at 1:33
• @Rick: Not saying smallest ... that contains ...? – Tim Jun 3 '14 at 1:34

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.