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?

  • 1
    $\begingroup$ 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.) $\endgroup$ – Rick Decker Jun 3 '14 at 1:01
  • $\begingroup$ Thanks, @Rick. I didn't. What about context free langauges, context-sensitive langauges, recursive langauges, and recursively enumerable langauges? $\endgroup$ – Tim Jun 3 '14 at 1:08
  • $\begingroup$ 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).. $\endgroup$ – Rick Decker Jun 3 '14 at 1:30
  • $\begingroup$ @RickDecker: Ha, had I read that before starting to compose my answer, I could have saved me some trouble! $\endgroup$ – Raphael Jun 3 '14 at 1:33
  • $\begingroup$ @Rick: Not saying smallest ... that contains ...? $\endgroup$ – 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} $


    $\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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.