Carathéodory Extensions of Subclasses ofRegular Languages
Ryoma Sin’ya
Akita University
ryoma@math.akita-u.ac.jp

Abstract. A language L is said to be regular measurable if there exists
an infinite sequence of regular languages that “converges” to L. In [1], theauthor showed that, while many complex context-free languages are regular measurable, the set of all primitive words and certain deterministic
context-free languages are regular immeasurable. This paper investigates
general properties of measurability, including closure properties, decidability and different characterisation. Further, for a suitable subclass Cof regular languages, we show that the class of all C-measurable regular
languages has a good algebraic structure.

1

Introduction

How can we measure the volume of an object with a very complex shape? If
it can be wet, an easy way is to slowly and completely submerge the object
suspended by a thread in a rectangular tank filed with water, pull it out, andcalculate the amount of water that overflows from the reduced water level. The
amount of water that overflows is needed to “cover” the object, so it will be agood estimation of the volume of the object. It is a standard way in measure
theory to cover an object X ⊆ Rd with a set Y ⊇ X with good properties, calleda “basic set”, and use the measure of Y as an estimation (from outer) of themeasure of X.
For example, in the case of Lebesgue measure (cf. [2]), we define the length of
an interval I = [a, b], [a, b), (a, b], (a, b) as |I| = b − a, and call the direct product
B = I1 × · · · × Id of d intervals as a box (with |B| = |I1 | × · · · × |Id |), and regard
a countable union of boxes as a basic set. The Lebesgue outer measure of a set
X ⊆ R is defined as
(∞
)
∞
X
[
m∗ (X) = inf|Bn |Bn ⊇ X; Bn is a box for each n ≥ 1 ,
n=1

n=1

S∞
i.e., the lower bound on the volume required to cover X by a basic set n=1 Bn .
X is said to be Lebesgue measurable if it satisfies the following so-called
Carathéodory’s condition (where X is the complement of X):∀S ⊆ Rdm∗ (S) = m∗ (S ∩ X) + m∗ (S ∩ X).

Actually, for subsets of the set of natural numbers N (3 0), we can apply thismeasure theoretic approach. In [3], Buck defines the density of an arithmetic
progression (AP for short) A = {pn + q | n ∈ N} where p, q ∈ N 1 as d(A) = 1/p(d(A) = 0 if p = 0), regards a finite union of arithmetic progressions as a basic
set, and defines the outer density of X ⊆ N as
)
( k
k
[
X
∗
An ⊇ X; k ∈ N, An is an AP for each n ∈ [1, k] .
d (X) = infd(An )
n=1

n=1

As like the Lebesgue measurability, X ⊆ N is said to be measurable if it satisfies
the Carathéodory’s condition∀S ⊆ Nd∗ (S) = d∗ (S ∩ X) + d∗ (S ∩ X),

and Buck called d∗ (X) the measure density of X in this case.
Regular measurability (REG-measurability) proposed in [1] is an adoptionof the Buck’s measure density for formal languages: we define the density of alanguage L ⊆ A∗ , regards a regular language as a basic set, and define the measurability of a language via outer and inner density (precise definition appears
in the next section). The main motivation of [1] is, not just to generalise Buck’s
measure density, but also to tackle a long-standing open problem so-called primitive words conjecture. Some non-trivial partial results can be found in [1], which
we will briefly describe in the next section. Regular measurability is an emergent notion and hence its theory is not well developed yet. In fact, it is fair tosay that very little is known about the class of all regular measurable languages(regular measurable context-free languages, respectively). This paper investigates fundamental properties of regular measurability (and C-measurability fora general language class C) like as closure properties, decidability and different
characterisation. Moreover, as a “miniature” of regular measurability, for some
subclass C of regular languages, we investigate C-measurability. While the classof all regular measurable languages (regular measurable context-free languages)
has a complex structure and it is somewhat hard to analyse, for some suitablesubclass C (called local variety) of regular languages, we will show that the classof all C-measurable regular languages has a good algebraic structure and moreeasier to analyse.
Our contribution and the organisation of the paper
In this paper, all theorems/corollaries without citation are new (as much as weknow), and main results consist of three kinds: (I) Give some new examplesof regular (im)measurable languages (Theorem 5–6, Corollary 1 in Section 2).
(II) Show some closure properties, an undecidability result (modulo a certain
conjecture), and a different characterisation via the Carathéodory’s conditionof C-measurability for a general language class C (Theorem 7–10 in Section 3).
(III) Examine Carathéodory extensions of some local varieties of regular languages (Theorem 13–16 in Section 4). We also discuss future work and pose few
open problems in Section 5.
1

Here p can be 0 and we call a singleton {q} arithmetic progression in this case.

2

Density and Measurability

This section provides the precise definitions of density and measurability. In
Section 2.3, we briefly describe results in [1], and also give some new examplesof regular measurable/immeasurable languages.
2.1

Density of formal languages

For a set X, we denote by #(X) the cardinality of X. We denote by N the set of
natural numbers including 0. For an alphabet A, we denote the set of all words(all non-empty words, respectively) over A by A∗ (A+ , respectively). For a wordw ∈ A∗ and a letter a ∈ A, |w|a denotes the number of occurrences of a in w.
A word v is said to be a subword of a word w if w = xvy for some x, y ∈ A∗ .
For a language L ⊆ A∗ , we denote by L = A∗ \ L the complement of L. We saythat L is co-finite if its complement is finite. A language L is said to be dense if
L ∩ A∗ wA∗ 6= ∅ holds for any w ∈ A∗ . L is not dense means L ∩ A∗ wA∗ = ∅ forsome word w by definition, and such word is called a forbidden word of L.
∗
Definition 1. Let L ⊆ A∗ be a language. The density δA(L) of L over A isdefined asn−1
1 X # L ∩ Ak∗
δA (L) = limn→∞ n#(Ak )
k=0∗
if its exists, otherwise we write δA(L) = ⊥ and say that L does not have a density.
∗∗
L is called null if δA (L) = 0, and conversely L is called co-null if δA(L) = 1.

The following observation is basic. See Chapter 13 of [4] for more details.
∗∗
Lemma 1. Let K, L ⊆ A∗ with δA(K) = α, δA(L) = β. Then we have:(1) α ≤ β if K ⊆ L.
∗∗∗
(A∗ \ K) = 1 − α.
(2) δA(L \ K) = β − α if K ⊆ L. In particular, δA(K) = δA∗∗(3) δA (K ∪ L) ≤ α + β if δA (K ∪ L) 6= ⊥.
∗(4) δA(K ∪ L) = α + β if K ∩ L = ∅.
|w|∗∗(5) δA (wK) = δA(Kw) = α/#(A) for each w ∈ A+ .
Example 1. Here we enumerate a few examples of densities of languages.
∗

n

∩A )
(1) Consider (AA)∗ the set of all words with even length. Because #((AA)#(An )∗∗
is 1 if n is even otherwise 0, clearly δA ((AA) ) = 1/2 holds.
(2) For each word w, the language A∗ wA∗ , i.e., the set of all words that containw as a subword, has density 1 (co-null). This fact is sometimes called infinitemonkey theorem. A language L having a forbidden word w is always null;∗∗since A∗ wA∗ ⊆ L holds by definition, we have δA(A∗ wA∗ ) ≤ δA(L) which∗implies δA (L) = 1 by infinite monkey theorem. Thus L is null.

(3) The following languageL⊥ = {w ∈ A∗ | 3n ≤ |w| < 3n+1 for some even number n}∗does not have a density (δA(L⊥ ) = ⊥). The proof is as follows. The densityof L⊥ is the limit (when n → ∞) of the fraction
n−1
1 X # L⊥ ∩ Ai
(1)
n i=0
#(Ai )

if it exists by definition. Consider n = 3k for some even number k and let
0 ≤ α ≤ 1 be the value of the fraction (1) of n = 3k , then the value (1) ofn = 3k+1 satisfiesk 3k+1 −1 
3 −1X1
1  X # L⊥ ∩ Ai+
1 = k+1 (3k α + 3k+1 − 3k )
k+1
i
3
#(A )
3
k
i=0
i=3

=

α+2
α+3−1
=
≥ 2/3.
3
3

Conversely, consider n = 3k for some odd number k and let 0 ≤ β ≤ 1 be
the value (1) of n = 3k , then the value (1) of n = 3k+1 satisfiesk 3k+1 −1 
3X
−1
i
X
# L⊥ ∩ A
1 
3k β
β0 = k+1 = ≤ 1/3.
+
k+1
i
3
#(A
)
3
3
k
i=0
i=3

Hence the value (1) could be larger than 2/3 and smaller than 1/3 infinitely∗(L⊥ ) diverges.
tumany times so that δA
Example 1 shows us that, for some language, its density is either zero orone, for some, like (AA)∗ , a density could be a rational number like 1/2, andfor some, like L⊥ a density may not even exist. However, the following theorem
tells us that all regular languages do have densities.
Theorem 1 (cf. Theorem III.6.1 of [5]). Every regular language has a density and it is rational.
Also, for the class of regular languages, two notions “not null” (a measure
theoretic largeness) and “dense” (a topological largeness) are equivalent.
Theorem 2 ([6]). A regular language L is not null if and only if L is dense.
2.2

C-measurability of formal languages∗

A language class C is a family of languages {CA }A: finite alphabet where CA ⊆ 2A
for each A and CA ⊆ CB for each A ⊆ B. We simply write L ∈ C if L ∈ CA forsome alphabet A. We denote by REG and CFL the class of regular languages
and context-free languages, respectively.
We now introduce the notion of C-measurability which is a formal language
theoretic analogue of Buck’s measure density [3].

Definition 2 ([1]). Let C be a class of languages. For a language L ⊆ A∗ , wedefine its C-inner-density µC (L) and C-outer-density µCA (L) over A as
A∗∗
µC (L) = sup{δA(K) | K ⊆ L, K ∈ CA , δA(K) 6= ⊥},A∗∗(K) | L ⊆ K, K ∈ CA , δA(K) 6= ⊥}.
µCA (L) = inf{δA

A language L is said to be C-measurable over A if µC (L) = µCA (L) holds, andA
we simply write µCA (L) as µCA (L) in this case. We say that an infinite sequence(Ln )n of languages over A converges to L from inner (from outer, respectively)∗∗
if Ln ⊆ L (Ln ⊇ L, respectively) for each n and limn→∞ δA(Ln ) = δA
(L).
Remark 1. Both density and C-measurability depends on the alphabet. For example, any language L ⊆ A∗ is of density zero over B ) A. Also, any language
L ⊆ A∗ is REG-measurable over B ) A: clearly ∅ ⊆ L ⊆ (B \ {b})∗ holds
for b ∈ (B \ A) and hence µREG (L) = µREGB (L) = 0 ((B \ {b})∗ has a forB
bidden word b hence it is null over B by infinite monkey theorem), i.e.REGmeasurable over B. Hereafter, we mainly consider density and C-measurability
over the minimum alphabet for each language L, i.e., the minimum alphabet
A satisfying L ⊆ A∗ . We sometimes omit the subscript of µREG (L), µREGA (L)A
like µREG (L), µREG (L), and we simply say “L is of density one” or “L is Cmeasurable”. In this case the considered alphabet is always the minimum one.
The following basic lemmata will be used in the next section.
Lemma 2 (cf. [1]). Let K, L ⊆ A∗ be two languages.
∗∗∗(K) = ⊥ implies(K) ≤ µCA (K) if δA(K) 6= ⊥. In particular, δA(1) µC (K) ≤ δA
A
K is C-immeasurable.
(2) µCA (K) ≤ µCA (L) if K ⊆ L.
(3) µCA (K ∪ L) ≤ µCA (K) + µCA (L) if C is closed under union.
∗∗(K) 6= ⊥.
(K) if K ∈ C and δA(4) µCA (K) = δA

Lemma 3 (cf. [1]). Let C be a language class closed under complementation. A
language L ⊆ A∗ is C-measurable if and only ifµCA (L) + µCA (L) = 1.
2.3

(2)

Examples of REG-measurable/immeasurable languages

In this subsection we describe several examples of REG-(im)measurable languages. In [1], it is shown that many complex context-free languages are still
REG-measurable summarised as follows.
Theorem 3 ([1]). Following context-free languages are all non-regular but REGmeasurable.
(1) D = {w ∈ {a, b}∗ | |w|a = |w|b , |u|a ≥ |u|b for every prefix u of w}.
(2) P = {w ∈ {a, b}∗ | w is a palindrome}.

(3) O3 = {w ∈ {a, b, c}∗ | |w|a = |w|b or |w|a = |w|c }.
(4) O4 = {w ∈ {x, x, y, y}∗ | |w|x = |w|x or |w|y = |w|y }.
(5) G = {an1 ban2 b · · · ank b | k ≥ 1, ni 6= i for each 1 ≤ i ≤ k}.
(6) K = S1 {c}A∗ ∪ S2 {c}A∗ where A = {a, b, c} andS1 = {a}{bi ai | i ≥ 1}∗

S2 = {ai b2i | i ≥ 1}∗ {a}+ .

The semi-Dyck language D and the palindromes P are classical examples of
non-regular languages. Flajolet [7] showed that the language O3 and O4 areinherently ambiguous. Flajolet also showed that the generating function of G is
not algebraic [8] and thus it is an inherently ambiguous context-free language
due to the well-known Chomsky–Schützenberger theorem [9] stating that thegenerating function of every unambiguous context-free language is algebraic. The
language K defined by Kemp [10] is the first example of a context-free languagewith transcendental density. While several complex context-free languages likeG or K are REG-measurable, the following theorem says certain deterministic
context-free languages and the set of all primitive words are REG-immeasurable.
Theorem 4 ([1]). The following languages over A = {a, b} are all REG-immeasurable.
(1) Mn = {w ∈ A∗ | |w|a > n · |w|b } for each n ≥ 1.
(2) The set Q of all primitive words. Here w ∈ A+ is said to be primitive if it can
not be represented as a power of any shorter words, i.e., for every v ∈ A+
and n ∈ N, v n = w implies v = w and n = 1.
In particular, the above languages are REG-immeasurable in a strong sense as
follows: µREG (Mn ) = µREG (Q) = 0 and µREG (Mn ) = µREG (Q) = 1 for eachn ≥ 2.
In [1] the author originally conjectured that there is no context-free language like
Q: if a context-free language L is co-null, then it can be somehow “approximated”
by regular languages from inner, i.e., µREG (L) > 0. If this conjecture was true,
then the primitive words conjecture “Q is not context-free” posed by Dömösi,
Horváth and Ito [11] was true, too. However, the author found a counterexample
M2 and hence this naı̈ve approach did not work (still, this approach has somepossibility, see the last section of [1] for details).
Now we give three new examples of REG-(im)measurable languages. The
following indexed language is not context-free, but REG-measurable.
nTheorem 5. Lexp = {a2 | n ∈ N} is REG-measurable over A = {a}.
∗Proof. Clearly, δA(Lexp ) = 0 holds hence it is enough to construct a sequenceof regular languages that converges to Lexp from outer. For each k ≥ 1, a∗
regular language Lk = (ak )∗ ∪ {an | 0 < n < k} satisfies δA(Lk ) = 1/k∗
2n(limk→∞ δA (Lk ) = 0, in particular). We show that a ∈ L2k holds for eachk ≥ 1 and n ∈ N (i.e., Lexp ⊆ L2k ). The case 2n < 2k is clear by definitionnthus consider the case 2n ≥ 2k . In this case, 2n = 2k · 2n−k holds hence a2knkis the 2n−k times repetition of a2 which means a2 ∈ (a2 )∗ ⊆ L2k . Thus thesequence (L2k )k≥1 converges to Lexp from outer.
tuThe next theorem tells us that REG-measurable languages exist for each real
number between 0 and 1.
Theorem 6. Let A be an alphabet including at least two letters. For each real
number 0 ≤ α ≤ 1, there exists a REG-measurable language L over A withdensity exactly α.
Proof. Proof. Consider the case A = {a, b} (a general case can be shown similarly).PLet (αn )n≥1 (where each αi ∈ {0, 1}) be the binary expansion of α ∈ [0, 1]:∞
α = n=1 αn 2−n . Define K0 = ∅, M0 = A∗ and define Kn , Mn inductively as
follows:((bn−1 aA∗ ∪ Kn−1 αn = 1
Mn−1
αn = 1
Mn =
Kn =
n−1
∗
Kn−1
αn = 0
Mn−1 \ baA αn = 0
Clearly, Kn and Mn are regular and Kn ⊆ Kn+1 ⊆ Mn+1 ⊆ Mn holds for each
∗ n−1
n. We have bn−1 aA∗ ∩ bm−1 aA∗ = ∅ for each n 6= m, and δA(baA∗ ) = 2−n
by Lemma 1-(5). Hence by using Lemma 1-(2) and (2) we can conclude that∗
δA(Kn ) =nXi=1

αn 2−n∗δA(Mn ) = 1 −nX(1 − αn )2−n

i=1

S
T
holds. Thus (Kn , Mn )n converges to the limit language L = n∈N Kn = n∈N Mn∗∗∗
whose density is δA(L) = limn→∞ δA(Kn ) = limn→∞ δA(Mn ) = α.
tuFinally, by Lemma 2-(1) we have the following REG-immeasurable language.
Corollary 1. L⊥ defined in Example 1-(3) is REG-immeasurable.

3

Closure Properties and Carathéodory’s Condition

In this section we investigate general properties of C-measurability. First weshow that C-measurability is closed under Boolean operations and left-and-rightquotients, with some density condition. This fact plays important role in thenext section.
Theorem 7. Let C be a language class closed under Boolean operations. If L, K
are C-measurable, and if every language obtained by a finite Boolean combinationof languages in C ∪{L, K} has a density, then the complement L, the union L∪K
and the intersection L ∩ K are also C-measurable.
Proof. C is closed under Boolean operations by assumption, thus a language L
is C-measurable if and only if L is C-measurable by Lemma 3. Thus it is enoughto show that L ∪ K is C-measurable if L and K are. Let (Ln )n and (Kn )n areconvergent sequence from inner to L and K, respectively. Since C is closed undertaking union, (Ln ∪ Kn )n is a sequence of languages in C. We show that thissequence converges to L ∪ K from inner. For any /2 > 0 there exists δ such that

∗
∗
∗
∗
δA
(L) − δA
(Ln ), δA(K) − δA(Kn ) < /2 for each n > δ, thus by Lemma 1-(2) we
have
∗
∗
∗
∗
∗
∗
(δA
(L) − δA
(Ln )) + (δA(K) − δA(Kn )) = δA
(L \ Ln ) + δA
(K \ Kn ) < .

By assumption, (L \ Ln ) ∪ (K \ Kn ) has a density, hence by the subadditivity of∗δA(Lemma 1-(3))∗∗∗δA((L \ Ln ) ∪ (K \ Kn )) ≤ δA
(L \ Ln ) + δA
(K \ Kn ) < 

holds. Clearly, (L ∪ K) \ (Ln ∪ Kn ) ⊆ (L \ Ln ) ∪ (K \ Kn ) holds and hence∗
δA((L ∪ K) \ (Ln ∪ Kn )) < , which means that (Ln ∪ Kn )n converges to L ∪ Kfrom inner. We can also construct an convergent sequence to L ∪ K from outerin the same way.
tu
Theorem 8. Let C be a language class closed under left quotients (right quotients, respectively). If L is C-measurable, and if the left quotient a−1 L (the rightquotient La−1 , respectively) has a density, then it is also C-measurable.
Proof. For a C-measurable language L over A, we show that a−1 L is also Cmeasurable (La−1 can be shown by the same way). By definition, there is aconvergent sequence (Kn , Mn )n to L. We show that (a−1 Kn , a−1 Mn )n converges
to a−1 L.
For simplicity, we consider the case A = {a, b} (a general case can be shown
similarly). For each a ∈ A we have L ∩ aA∗ = aa−1 L and hence L can be
written as L = aa−1 L ∪ bb−1 L ∪ (L ∩ {ε}). By assumption aa−1 L and bb−1 L
have density. Because aa−1 L and bb−1 L are mutually disjoint, by the additivity∗(Lemma 1-(4)) we have
of δA
∗
∗
∗
δA
(L) = δA(aa−1 L) + δA
(bb−1 L).

(3)∗
Kn ⊆ L holds for each n hence we have a−1 Kn ⊆ a−1 L and δA(a−1 Kn ) ≤∗−1δA (a L). Because (Kn )n is a convergent sequence to L from inner, for any∗∗(Kn ) < /2 holds for every n > δ.
(L) − δA
/2 > 0 there exists δ such that δA
Thus from Equality (3) we can deduce that
∗
∗
∗
∗
∗
∗
δA
(L) − δA(Kn ) = δA
(aa−1 L) − δA(aa−1 Kn ) + δA
(bb−1 L) − δA
(bb−1 Kn ) <2∗∗ −1 0holds for every n > δ. We know δA(cc−1 L0 ) = δA(c L )/2 for any c ∈ {a, b}
0and L by Lemma 1-(5), the above inequality can be transformed as

1 ∗ −11 ∗ −1∗∗ −1(δ (a L) − δA
(a−1 Kn )) + (δA(b L) − δA(b Kn )) < .
2 A
2
2
∗
∗
Hence we can conclude that δA(a−1 L) − δA
(a−1 Kn ) <  for every n > δ, i.e.,−1−1(a Kn )n is a convergent sequence to a L from inner. We can show that(a−1 Mn )n converges to L from outer by the same way.
tuCorollary 2. Let C ⊆ D be language classes where C is closed under Boolean
operations and left-and-right quotients and every language in D has a density.
Then C-measurability in D is preserved under Boolean operations and left-andright quotients.
An application of Theorem 8 is a proof of the undecidability of
REG-measurability for context-free languages, modulo the following conjecture.
Conjecture 1. If a context-free language L has a density, then its quotients a−1 L
and La−1 also have densities.
Theorem 9. If Conjecture 1 is true, then it is undecidable whether a given
context-free grammar generates REG-measurable language or not.
Proof. The class CFL is closed under left-and-right quotients, hence by Theorem 8 the class P = {L ∈ CFLA | L is REG-measurable}A is also closed underleft-and-right quotients. It is clear that REG ⊆ P holds, and by Theorem 4-(1)there is REG-immeasurable context-free language M2 , i.e., P ( CFL. Because
the universality problem for CFL is undecidable, the REG-measurability is also
undecidable for CFL by the well-known Greibach’s theorem [12].
tu
We conclude this section by giving the following Carathéodory’s condition
characterisation of REG-measurability. The proof is almost same with one ofLebesgue measurability (cf. [2]), albeit that requires some density condition which
is formal language theoretic.
Theorem 10. Let C be a class of languages closed under Boolean operations
and let L ⊆ A∗ be a language. If every language obtained by a finite Boolean
combination of languages in C ∪ {L} has a density, then L is C-measurable if
and only if the following Carathéodory’s condition holds:∀X ⊆ A∗µC (X) = µC (X ∩ L) + µC (X ∩ L).

(4)

Proof. If L satisfies the Carathéodory condition (4), then we obtain µC (A∗ ) =1 = µC (L) + µC (L) when X = A∗ , thus by Lemma 3, L is C-measurable because
C is closed under complementation by assumption.
Now we show the converse direction. Assume L is C-measurable. For any
language X ⊆ A∗ and for any  > 0, by the definition of µC , there exists K ∈ C∗such that X ⊆ K and δA(K) ≤ µC (X)+. Here L, K and K are all C-measurable,
and by assumption K ∩ L and K ∩ L have densities. Hence, by Theorem 7,
K ∩ L and K ∩ L are C-measurable. Because K = (K ∩ L) ∪ (K ∩ L) and(K ∩ L) ∩ (K ∩ L) = ∅,∗∗∗δA(K) = δA
(K ∩ L) + δA(K ∩ L)∗holds by the additivity of δA(Lemma 1-(4)). Hence we have∗∗∗µC (X) ≥ δA(K) −  = δA(K ∩ L) + δA(K ∩ L) − ≥ µC (X ∩ L) + µC (X ∩ L) − .

Because  > 0 is taken arbitrarily, we can conclude thatµC (X) ≥ µC (X ∩ L) + µC (X ∩ L)
holds. The reverse direction ≤ of the above inequality is directly obtained by
the subadditivity of µC (Lemma 2-(3)).
tu

4Carathéodory Extensions of Local Varieties

In this section, as a “miniature” of REG-measurability, we investigate
C-measurability for some subclass C of REG. The considered subclasses of regular
languages here are so-called local varieties, which enjoy good closure properties
and have rich algebraic structure. First we introduce some background materials
from algebraic language theory.
4.1

Local varieties and an Eilenberg-type theorem

Due to the space limitation, we assume that the author has a basic knowledgeof algebraic language theory (e.g., syntactic monoids and morphism, etc. cf. [13,14]). For a language L over A, we denote its syntactic monoid by Synt(L) and its
syntactic morphism by ηL : A∗ → Synt(L). A monoid M is said to be aperiodic, if
there is k ≥ 1 such that xk = xk+1 for any x ∈ M . M is called zero if it contains
zero element 0: 0 · x = x · 0 = 0 for all x ∈ M . Further, a zero semigroup S iscalled nilpotent if there is k ≥ 1 such that xk = 0 for any x ∈ S. A non-empty
subset I ⊆ M is called ideal if M · I · M ⊆ I. An ideal I is said to be minimal if
no proper subset of I is an ideal. It is well-known that any finite monoid has aunique minimal ideal (cf. [14]).
The main targets in the next subsection are classes of regular languages withsome good closure properties as follows.
Definition 3 (cf. [15]). A family C ⊆ REGA of regular languages over A iscalled local variety if it is closed under Boolean operations and left-and-rightquotients. A family V of finite monoids generated by A is called local pseudovariety if it is closed under quotients and subdirect products.
Theorem 11 (Eilenberg-type theorem for local varieties [16]). For eachA, there is a lattice isomorphism between the class of all local varieties and theclass of all local pseudovarieties.
This Eilenberg-type theorem roughly states that: if a class of languages issomewhat “robust” (i.e., enjoys good closure properties), then it could be characterised by an algebraic way (at least there should exist the corresponding local
pseudovariety), and vice versa. We now enumerate three examples of local varieties and corresponding local pseudovarieties (see Fig 1). A prominent example
of a local variety is star-free languages. A language L is said to be star-free if it
can be obtained by a finite combination of Boolean operations and concatenations of finite languages. The family SFA of all star-free languages over A forms
a local variety, and this class can be characterised in purely algebraic way as
follows.

Local Varieties

Local Pseudovarieties

regularfiniteCorrespondence?

star-freezero-oneaperiodic

zero
Extension RExt

finite co-finite(nilpotent)

Fig. 1. Relation between local varieties, extensions and local pseudovarieties.

Theorem 12 (Schützenberger’s theorem [17]).
The corresponding local pseudovariety of SFA is the class of aperiodic finite
monoids generated by A. Namely, L ∈ SFA if and only if Synt(L) is aperiodic.
Next we introduce two additional examples of local varieties. One is thefamily FINA of all finite and co-finite languages and another one is the family
ZOA of all regular languages with density either zero or one. FINA and ZOAform a local variety, respectively. In his Volume B [18], Eilenberg showed thatthe class of all finite nilpotent semigroups form a pseudovariety (of semigroups)
and its corresponding +-variety of languages is exactly the class of all finite andco-finite languages. The corresponding local pseudovariety of ZOA is the familyof all finite zero monoids (cf. [6]).
4.2

Extension as a closure operator

In this subsection we mainly consider “extensions” of local varieties. All results
are summarised in Fig. 1. First we introduce necessary notation.
∗

Definition 4. For a family C ⊆ 2A of languages over A, we define its(Carathéodory) extension as
ExtA (C) = {L ⊆ A∗ | L is C-measurable},and define its regular extension as
RExtA (C) = ExtA (C) ∩ REGA .
Observe that this extension operator is a closure as follows.
Theorem 13. ExtA is a closure operator, i.e., it satisfies the following three∗properties for each C, D ⊆ 2A .
extensive:C ⊆ ExtA (C).

monotone: C ⊆ D implies ExtA (C) ⊆ ExtA (D).
idempotent: ExtA (ExtA (C)) = ExtA (C).
Proof. The extensivity and monotonicity are clear from the definition. To show
the idempotency, consider L ∈ ExtA (ExtA (C)). In this case, there exists an
infinite sequence (Kn , Mn )n of pairs of languages in ExtA (C) that converges to L.
For each n, Kn and Mn belong to ExtA (C), thus there exist a sequence (K(n,i) )iof languages in C that converges to Kn from inner and a sequence (M(n,i) )i of
languages in C that converges to Mn from outer. Then the infinite sequence(K(n,n) , M(n,n) )n of pairs of languages in C converges to L,i.e., L ∈ ExtA (C). tu
In the previous section, we showed that the C-measurability is closed under
Boolean operations and left-and-right quotients if C is closed under these operations and every language in C have a density (Corollary 2). Because every
regular language have a density (Theorem 1), we have the following corollary.
Corollary 3. For any local variety C ⊆ REGA over A, RExtA (C) ⊇ C is also a
local variety over A, i.e., RExtA is a closure operator over the class of all local
varieties.
Clearly, any FINA -measurable language is either finite or co-finite. A similarargument can be applied for ZOA . Thus RExtA does not properly extend these
two local varieties.
Theorem 14. RExtA (FINA ) = FINA and RExtA (ZOA ) = ZOA for each A.
Furthermore, for a unary alphabet A = {a}, it is well-known that SFA =ZOA = FINA , hence we have the following as a corollary.
Corollary 4. RExtA (SFA ) = SFA = ZOA = FINA for A = {a}.
The situation is different for the case #(A) ≥ 2. As we explained in Remark 1,
if #(A) ≥ 2, RExtA (SFA ) can contain any regular language over B ( A hence
RExtA (SFA ) ) SFA (RExtA (SFA ) 3 (aa)∗ ∈/ SFA , in particular). The next
theorem says, however, RExtA (SFA ) can not contain some regular languages
over A like (AA)∗ .
∗Theorem 15. If a star-free language L ∈ SFA satisfies δA(L) > 0, then L
contains words of even and odd length.

Proof. Consider the syntactic monoid Synt(L), the syntactic morphism ηL :A∗ → Synt(L) and the syntactic image S = ηL (L) of L. Because L is regular, Synt(L) is finite. Hence it has a unique minimal ideal K ⊆ Synt(L). Let wx
be a word whose syntactic image ηL (wx ) is x for each x ∈ Synt(L).
∗∗The assumption δA(L) > 0 implies S ∩ K 6= ∅, because δA(η −1 (Synt(L) \∗K)) = 0 holds; for each k ∈ K and x, y ∈ A , we have ηL (xwk y) = ηL (x) · k ·ηL (y) ∈ K and hence η −1 (Synt(L)\K)∩A∗ wk A∗ = ∅ which implies η −1 (Synt(L)\K) is null by infinite monkey theorem. Thus L is not null implies its syntactic
image S contains at least one element of K, say, t ∈ S ∩ K.

∗Clearly, δA(η −1 (K)) = 1 holds and hence η −1 (K) contains some word woddof odd length. Let modd = ηL (wodd ) be its syntactic image. By Schützenberger’s
theorem (Theorem 12), Synt(L) is aperiodic thus there is some i ≥ 1 such that
miodd = mi+1
odd . By the minimality of the ideal K, there exist x, y ∈ Synt(L) suchthat x · miodd · y = t (if not, the ideal Synt(L) · miodd · Synt(L) generated by miodd
does not contain t hence it should be a proper subset of K). Then two words
i+1
i
wx wodd
wy and wx wodd
wy has the same syntactic imagei+1iηL (wx woddwy ) = x · miodd · y = t = x · mi+1
odd · y = ηL (wx wodd wy ),thus both belong to L. Because the length of wodd is odd, the lengths of these
two words are different modulo 2.
tu
The above theorem tells us that any star-free subset of (AA)∗ is null and any
star-free superset of (AA)∗ is co-null, thus we have the following corollary.
Corollary 5. (AA)∗ ∈/ RExtA (SFA ) for any A. In particular, µSF ((AA)∗ ) = 0
A∗and µSFA ((AA) ) = 1. Further, SFA ( RExtA (SFA ) ( REGA if #(A) ≥ 2.
We are not aware what the associated local pseudovariety of this new local
variety RExtA (SFA ) yet, but, we can say that RExtA (SFA ) always contains all
zero-one regular languages.
Theorem 16. RExtA (SFA ) ⊇ ZOA for any A.
Proof. The case #(A) = 1 follows from Theorem 4. We show this for a general∗(L) = 0 without loss of genalphabet A. Let L ∈ ZOA and we can assume δA
erality. By Theorem 2, L is null implies there is some forbidden word w of L:
L ∩ A∗ wA∗ = ∅. Hence L ⊆ A∗ wA∗ holds and µSF (L) = µSFA (L) = 0.
t
u
A

5

Future Work and Open Problems

We have investigated general properties of C-measurability, and examine how theextension operator RExtA extends certain local varieties of regular languages. An
immediate future work is to give an algebraic characterisation of RExtA (SFA ).
We are also interested whether we can characterise the associated extension operator of local pseudovarieties of finite monoids MExtA (V) = F (RExtA (F −1 (V)))
in purely algebraic way, where F is the lattice isomorphism stated in Theorem 11. One of the ideal goals is to understand the class of REG-measurable
context-free languages. However, it looks like a bit difficult since the theory ofdensities of context-free languages is not well developed yet (e.g., Conjecture 1).
Actually, we are not aware whether there is a context-free language that do nothave a density (L⊥ in Example 1-(3) is not context-free). More open problems
related to REG-measurability and context-free languages were posed in [1].
Acknowledgements: This work was supported by JSPS KAKENHI Grant
Number JP19K14582.

References
1. Sin’ya, R.: Asymptotic approximation by regular languages. In: Current Trends
in Theory and Practice of Computer Science. (2021) 74–88
2. Tao, T.: An Introduction to Measure Theory. Graduate studies in mathematics.
American Mathematical Society (2013)
3. Buck, R.C.: The measure theoretic approach to density. American Journal of
Mathematics 68(4) (1946) 560–580
4. Berstel, J., Perrin, D., Reutenauer, C.: Codes and Automata. Encyclopedia of
Mathematics and its Applications. Cambridge University Press (2009)
5. Salomaa, A., Soittola, M.: Automata Theoretic Aspects of Formal Power Series.
Springer-Verlag New York, Inc., Secaucus, NJ, USA (1978)
6. Sin’ya, R.: An automata theoretic approach to the zero-one law for regular languages. In: Games, Automata, Logics and Formal Verification. (2015) 172–185
7. Flajolet, P.: Ambiguity and transcendence. In: Automata, Languages and Programming, Berlin, Heidelberg, Springer Berlin Heidelberg (1985) 179–188
8. Flajolet, P.: Analytic models and ambiguity of context-free languages. TheoreticalComputer Science 49(2) (1987) 283–309
9. Chomsky, N., Schützenberger, M.: The algebraic theory of context-free languages.
In: Computer Programming and Formal Systems. Volume 35. (1963) 118–161
10. Kemp, R.: A note on the density of inherently ambiguous context-free languages.
Acta Informatica 14(3) (1980) 295–298
11. Dömösi, P., Horváth, S., Ito, M.: On the connection between formal languages andprimitive words. In: First Session on Scientific Communication. (1991) 59–67
12. Greibach, S.A.: A note on undecidable properties of formal languages. Mathematical systems theory 2 (1968) 1–6
13. Lawson, M.V.: Finite Automata. Birkhäuser (2005)
14. Pin, J.E.: Mathematical foundations of automata theory (draft)
15. Adámek, J., Milius, S., Myers, R.S.R., Urbat, H.: Generalized eilenberg theorem i:
Local varieties of languages. In: Foundations of Software Science and Computation
Structures. (2014) 366–380
16. Gehrke, M., Grigorieff, S., Pin, J.: Duality and equational theory of regular languages. In: Automata, Languages and Programming. (2008) 246–257
17. Schützenberger, M.P.: On finite monoids having only trivial subgroups. Information and Control 8(2) (1965) 190–194
18. Eilenberg, S., Tilson, B.: Automata, languages and machines. Volume B. Pure andapplied mathematics. Academic Press, New-York, San Franciso, London (1976)