正則言語で極限的に近似可能な言語について
新屋

良磨 1

1 秋田大学

数理科学コースryoma@math.akita-u.ac.jp
概要
著者は [21] において正則可測性という概念を導入し，多くの複雑な文脈自由言
語が正則可測である一方，「原始語全体の集合」と言う組合せ論的に重要な言語が強い意
味で非可測であることを示した．ある言語 L が正則可測であるとは，直感的には L が正則言語でいくらでも近似できる，すなわち L に「収束」する正則言語の無限列が存在することを言う．
本論文では [21] で考察されていなかった，可測な言語全体の一般的な性質について議論する．また，正則言語の部分族であるいくつかの言語族について，その言語族において可測な言語全体の集合を明らかにする．

はじめに

1

非常に複雑な形をしたオブジェの体積を測るにはどうすれば良いだろうか？もしそれが水に濡らしても良いものであれば，手っ取り早い方法は水を満たした直方体の桶に糸で吊ったオブジェをゆっ
くりかつ完全に沈め，引き出し，減った水位から溢れた水の量を計算すれば良い．溢れた水の量はオブジェを「覆う」のに必要な水の量なので，それがオブジェの体積の良い目安になるだろう．このように，図りたい対象 X ⊆ Rd を基本集合と呼ばれる性質の良い集合 Y ⊇ X で覆い，Y の体積
を X の体積の目安 (外側からの近似値) とすることは測度論においても常套手段である．
例えば Lebesgue 測度においては，実数 a ≤ b ∈ R に対し区間 I = [a, b], [a, b), (a, b], (a, b) の長さを|I| = b − a で定め，d 個の区間の直積 B = I1 × . . . × Id を Rd の直方体 (体積は |B| = |I1 | × · · · × |Id |)と呼び，直方体の可算和を基本集合とみなす．集合 X ⊆ Rd の Lebesgue 外測度は
(∞
)
∞
X
[
m∗ (X) = inf|Bn |Bn ⊇ X; 各 n で Bn は直方体
n=1

n=1

として定義され，これは X を基本集合で「覆う」のに必要な体積の下限となっている．X が Lebesgue
可測であるとは，∀S ⊆ Rdm∗ (S) = m∗ (S ∩ X) + m∗ (S ∩ X)
を満たすことであった．上の条件は Carathéodory 条件と呼ばれる．
自然数全体 N(3 0) のような可算無限な集合に対しても，実はこの測度論的な手法は適用できる．
Buck [5] はまず自然数 p, q ∈ N に対して等差数列 A = {pn + q | n ∈ N} 1 の密度を d(A) = 1/p (ただし p = 0 の場合は d(A) = 0) と定め，等差数列の有限和を基本集合とみなし，X ⊆ N の外密度を
( k
)
k
X
[
d∗ (X) = infd(An )An ⊇ X; k ∈ N かつ各 n で An は等差数列
n=1

n=1

で定義した．Lebesgue 測度のときと同様に，Buck は X ⊆ N が Carathéodory 条件∀S ⊆ Nd∗ (S) = d∗ (S ∩ X) + d∗ (S ∩ X)

を満たすときに X は可測と言い，値 d∗ (X) を X の測密度 (measure density) と呼んだ．
1

p は 0 であっても良く，単元集合 {q} も等差数列と本論文では呼ぶ．

1

著者が [21] で導入した正則可測性は，Buck [5] の測密度の形式言語への拡張となっている．すな
わち，言語 L ⊆ A∗ に対して密度を定義し，正則言語を基本集合とみなし，外密度を経由して言語の可測性を定義する (厳密な定義は次節で行う)．A = {a} の場合は A∗ と N は同一視でき，この場合は正則可測性と Buck [5] の意味での可測性は精確に一致する．よって正則可測性は測密度の多次
元 (#(A) ≥ 2) かつ非可換 (一般に u, v ∈ A∗ で uv 6= vu) な一般化と見なすことができる．しかし，[21] では概念の一般化だけが動機ではなく，原始語予想と呼ばれる具体的かつ組合せ論的な未解決問題へのアプローチとして正則可測性を導入し，いくつか非自明な結果を得ている (次節の補足 17と補足 21 で簡単に説明する)．
[21] で導入した正則可測性は萌芽的な概念であり，まだまだ不明な点が多い．特に言語が正則可測であるとはどういうことか？
については，ほとんど明らかになってないと言って良い．[21] では様々な正則可測・正則非可測な具体例を構成しているが，一般の言語クラス C に対する C 可測な言語の性質 (例えば C 可測な言語全体のなすクラスの閉包性や決定可能性，可測性の別の特徴づけ，などなど) については考察されていなかった．本論文ではこれら基礎的な性質について注目し議論を進めていく．

貢献
本研究は [21] の継続であり，2.3 節では [21] の結果も簡単に解説する．本論文において引用のない定理・系は（著者の知る限り）全て新しい定理であり，本論文での貢献はおもに以下の４つからなる：

1. 密度を持たない言語・正則可測な言語の具体例 (定理 7，定理 18–19)
2. C 可測な言語全体の閉包性，正則可測性の (条件付きの) 決定不能性および C 可測性の Carathéodory
条件による特徴づけ (定理 22–26)．
3. 正則言語のいくつかの部分クラス C に対する C 可測性の考察 (定理 39–系 47)
4. 密度や C 可測性に関する問題と研究方針の提案 (予想 24，問題 49–51)．

構成
本論文の構成は本節を除くと４つの節からなり，それぞれ上記の貢献 (1)–(4) に対応する：続く 2
節では言語の密度および可測性を定義し，密度を持たない言語・正則可測な言語の具体例を紹介する．
その後 3 節で一般の言語クラス C に対して C 可測な言語全体のなすクラスの閉包性や Carathéodory
条件による特徴づけについて議論する．また、文脈自由言語に対する正則可測性の (ある予想の上での) 決定不能性を示す．4 節では，局所多様体と呼ばれる良い閉包性を満たす正則言語のいくつかの部分クラス C について注目し，それらのクラスにおける C 可測性を明らかにしていく．4 節では
代数的言語理論の道具が必要になるため，簡単な入門 (4.1 節) を含めた．本研究のまとめは 5 節で行い，それまでに得られた定理や予想から今後の課題や方針を述べて終わる．
本論文全体において，形式言語理論や代数的言語理論の知識がなくてもなるべく話の流れがわかるよう，基礎的な定義・概念は可能な限り省略せずに書き例も多めに載せている．

2

形式言語の密度と可測性

形式言語理論の必要最低限な基本用語を 2.1 節で導入する．続く 2.2 節で言語の密度を導入し，最後に 2.3 節で可測性を定義し正則可測・正則非可測な言語の例をいくつか紹介する．

2

2.1

形式言語の基本用語

形式言語理論において，アルファベットとは単に空でない有限集合のことを差し，アルファベッ
トの要素を文字と呼ぶ．以降，変数 A は常にアルファベットを表す. A 上の語とは A に属する文字
ai を有限個並べた列：a1 a2 · · · an である．語には連接 · という演算を考えることができ，2 つの語
u = a1 · · · ai , v = b1 · · · bj の連接 u · v は u と v を並べたものを表す：u · v = a1 · · · ai b1 · · · bj . 語 w を
n 個連接した文字列を wn で表す．例えば a3 = aaa で (ab)2 = abab である．語 w = a1 · · · an の長さを |w| で表す：|w| = n．ε で長さが 0 の語 (空語) を表す．集合 X の濃度を #(X) で表し，X が無限集合の場合は #(X) = ∞ とする (本論文に現れる無限集合は全て可算である)．また集合 X の補集合を X で表す．語 w = a1 · · · an 中の a ∈ A の個数を |w|a で表す：|w|a = #{i | ai = a}. A 上の全ての語の集合を A∗ で表し，A 上の長さが n である語の全ての集合を An で表す．語 w と u について，ある x, y ∈ A∗ が存在して w = xuy が成り立つときに w は u を部分語に含むと言う．言語
L に対して L ∩ A∗ wA∗ = ∅，すなわち L に属するどの語も w を部分語に含まないとき，L は w を禁句に持つと言う．逆に L が任意の語 w に対して L ∩ A∗ wA∗ 6= ∅ となるとき，L は稠密 (dense)2であると言う．
A 上の言語とは A∗ の部分集合のことを指す．すなわち L ⊆ A∗ となる L を言語と呼ぶ．任意の 2
つの言語 L, M の連接 L · M は以下のように語の連接を拡張して得られる：L · M = {uv ∈ A∗ | u ∈L, v ∈ M }. 言語 L に対し，Ln で言語 L の n 回の連接 L0 = {ε}, Ln = L · Ln−1 を表す．言語 L にn∗
対して，その Kleene 閉包 L∗ は L∗ = ∪∞n=0 L で定義される．A 上の言語 L に対し，文字列 u ∈ Aによる左商 u−1 L と右商 Lu−1 は次のように定義される：

u−1 L = {v ∈ A∗ | uv ∈ L}

Lu−1 = {v ∈ A∗ | vu ∈ L}

本論文における言語のクラス C とは全てのアルファベットで添字付けられた言語の族 C = {CA }A:アルファベット∗
で各アルファベット A ⊆ B に対して CA の要素は A 上の言語 (CA ⊆ 2A ) かつ CA ⊆ CB を満たすものである．ある A について L ∈ CA であることを単に L ∈ C と書けることにする．以下に，本論文の考察の中心となる言語クラスを導入する．
定義 1 (正則言語，有限・補有限言語，星無し言語). 言語 L について濃度が有限 (#(L) < ∞) の場
合は L を有限な言語と呼ぶ．言語 L が有限な言語に対する有限回の和集合・連接・Kleene 閉包の適用で表現できるとき，L を正則言語 (regular language) と呼ぶ．正則言語全体のクラスを REG で表す．ぶ．L の補集合 L が有限 (# L < ∞) の場合は L を補有限な言語 (coﬁnite language) と呼ぶ．
有限または補有限な言語全体のクラスを FIN で表す．言語 L が有限な言語に対する有限回の Bool
演算 (和集合・積集合・補集合) および連接の適用で表現できるとき，L を星無し言語 (ほしなし言語，star-free language) と呼ぶ．星無し言語全体のクラスを SF で表す．
正則言語のクラス REG は補集合に閉じているため，星無し言語は定義より正則言語でもある．
REG や FIN についてはよく知られているため例は不要であろうが，星無し言語 SF の例をいくつか挙げる．
例 2. 星無し言語はその名の通り Kleene 閉包 (演算 ∗ は “Kleene star” とも呼ばれる) を使わず，その代わりに補集合が使える体系で表現できる正則言語である．空集合 ∅ は有限集合であるため星無し言語であり，その補集合 A∗ = ∅ も星無し言語である．任意の文字列 w に対して単元集合{w} は有限集合であるため星無し言語である．{w} と A∗ はそれぞれ星無し言語であるため，それらの連接 wA∗ , A∗ w, A∗ wA∗ すなわち「w で始まる語全体」「w で終わる語全体」「w を部分語
2

位相空間論において位相空間 X の部分集合 S が X において稠密であるとは，S の閉包 (S を含む最小の閉集合)が X と一致することを言う．これは言語の場合において直感的には「L の部分語全体の集合 {v | ある u, w が存在して uvw ∈ L} が A∗ となる」すなわち稠密であることに対応している．より技術的に，A∗ を空間とみなし空集合と任意の語 w について A∗ wA∗ を開基として考えることで A∗ に位相が入り，言語 L が禁句を持たないという意味で稠密であることと，位相空間の意味で稠密であることが一致する (cf. [3] の演習問題 5.3)．

3

に含む語全体」もそれぞれ星無し言語である．そのため，アルファベット A = {a, b} に対して
(ab)∗ = {ε, ab, abab, ababab, . . .} は一見有限言語 {ab} に Kleene 閉包を使っているため星無し言語
ではないように思えるが，実は(ab)∗ = {ε} ∪ (A∗ aaA∗ ∩ A∗ bbA∗ ∩ aA∗ ∩ A∗ b)と有限言語 {ε} と星無し言語 A∗ aaA∗ , A∗ bbA∗ , aA∗ , A∗ b に対する有限回の補集合・和集合・積集合の適用で表現できるため，(ab)∗ は星無し言語である．その一方，(aa)∗ は星無し言語ではないが，その証明は難しく，4 節で導入する Schützenberger の定理 (定理 32) を用いて示すことができる．特に，(ab)∗ や aA∗ は有限でも補有限でもなく，(aa)∗ は明らかに正則言語であるため，FIN ⊊ SF ⊊ REG
が成り立つ．

2.2

密度

定義 3 (自然密度と密度 (cf. [21])). A 上の言語 L の自然密度 (natural density) とは次の極限#(L ∩ An )n→∞#(An )δA (L) = lim

であり，極限が収束しない場合は「L は自然密度を持たない」と言い δA (L) = ⊥ で表す．A 上の言
語 L の密度 (density) とは次の極限
n−1
1 X # L ∩ Ai∗
δA (L) = limn→∞ n#(Ai )
i=0∗ (L) = ⊥ で表す．
であり，極限が収束しない場合は「L は密度を持たない」と言い δA

補題 4 ([21]). 密度を持つ言語 K, L ⊆ A∗ について以下が成り立つ．
∗ (K) ≤ δ ∗ (L)．
(単調性) K ⊆ L なら δAA∗ (L \ K) = δ ∗ (L) − δ ∗ (K)．特に，δ ∗ (K) = 1 − δ ∗ (K)．
(差集合) K ⊆ L なら δAAAAA∗ (K ∪ L) 6= ⊥ なら δ ∗ (K ∪ L) ≤ δ ∗ (K) + δ ∗ (L)．
(劣加法性) δA
AAA∗ (K ∪ L) = δ ∗ (K) + δ ∗ (L)．
(加法性) K ∩ L = ∅ なら δA
A
A

(連接)

∗ (wL) = δ ∗ (L)/#(A)|w|
任意の w ∈ A+ に対して δA
A

初歩的な解析により，L が自然密度を持つ場合は密度も持ち，さらにその値は一致することがわかる．しかし，一般に逆は成り立たない．言語の密度の例をいくつか見てみよう．
∗ (L) は
例 5. 例えば言語 L = (AA)∗ に対しては δA (L) は収束しない (自然密度を持たない) が，δA
1/2 に収束する (密度を持つ)．言語 L が有限ならば定義より明らかにその自然密度は 0 になる．逆に，L が補有限ならば自然密度は 1 となる．
任意の語 w に対して，A∗ wA∗ すなわち「w を部分語に含む語全体の集合」の密度は 1 となる．この事実は無限の猿定理と呼ばれている．L が禁句を持つ場合，すなわちある w ∈ A∗ で L ∩ A∗ wA∗ = ∅∗ (L) = 1 よって δ ∗ (L) = 0 が成り立が成り立つときには，A∗ wA∗ ⊆ L のため無限の猿定理より δAA
つ．その一方，禁句を持たないなら密度が正になるかと言えばそういうことはない．例えば半 Dyck
言語 D = {w ∈ {a, b}∗ | |w|a = |w|b かつ任意の uv = w について |u|a ≥ |u|b }3 の密度は 0 である (簡
単な考察から # D ∩ A2n が n 番目の Catalan 数になることがわかり，n 番目の Catalan 数のオー
ダーが Θ(4n /n3/2 ) となる事実からわかる) が，任意の語 w ∈ {a, b}∗ についてある n, m ∈ N が取れて an wbm ∈ D とすることができるため D は禁句を持たない．
3
a を開き括弧「（」だと思い，b を閉じ括弧「）」だと考えると， w ∈ A∗ が D に属すというのは「w はきちんと括弧の対応が取れている」ことに他ならない4

∗ (L) = ⊥) で注意 6. 密度はアルファベットに依存する：一般に，A 上で密度を持たない言語 L (δA∗∗∗
あっても，B = A ∪ {c} (c ∈/ A) において L ∩ B cB = ∅ となり無限の猿定理から δB (L) = 0 と B
上では密度を持つ．以降，単に「L が密度を持つ」と言った場合には，常に L ⊆ A∗ となる最小の∗ (L) 6= ⊥ となることを意味する．
アルファベット A 上で δA

次は密度を持たない言語の例である．
定理 7. 任意のアルファベット A について，言語L⊥ = {w ∈ A∗ | ある偶数 n に対して 3n ≤ |w| < 3n+1 }は密度を持たない．

Proof. L⊥ の密度は定義より
1 X # L⊥ ∩ Ai
n#(Ai )
n−1


(1)

i=0

の n → ∞ での極限である．定義より，ある偶数 k に対して長さが 3k 以上 3k+1 未満の語は全て L⊥に属するため，n = 3k の分数 (1) の値を 0 ≤ α ≤ 1 とすると n = 3k+1 での分数 (1) の値は
 3k+1 −1 
k −1
3X
i
X
# L⊥ ∩ A
1
α+2
1 
α+3−1
1 = k+1 (3k α + 3k+1 − 3k ) =+=≥ 2/3 (2)
i
k+1
#(A )
3
3
3
3
k
i=0

i=3

となる．逆に，ある奇数 k に対して長さが 3k 以上 3k+1 未満の語は全て L⊥ に属さないため，n = 3kの分数 (1) の値を 0 ≤ β ≤ 1 とすると n = 3k+1 での分数 (1) の値は
 3k+1 −1 
k −1
3X
i
k
X
#
L
∩
A
1 
⊥
 = 3 β = β ≤ 1/3
0(3)+#(Ai )
3
3k+1
3k+1
k
i=0

i=3

となり，値 (1) は 2/3 以上の値と 1/3 以下の値をそれぞれ無限回取るため収束せず，したがって L⊥は密度を持たない．
このように，言語によっては密度を持たないものもあるが，次の定理は任意の正則言語は密度を持つことを保証する．
定理 8 (cf. [18] の Theorem III.6.1). L を A 上の正則言語とする．このときある自然数 c が存在して，d < c となる各自然数 d に対して次の極限が収束して有理数となる：
# L ∩ Acn+dlimn→∞#(Acn+d )系 9. 任意の正則言語は密度を持つ．
∗ (L) = 0 は等価である．
系 10. 任意の正則言語 L ⊆ A∗ に対して δA (L) = 0 と δA

さらに，正則言語においては「密度が 0 である」という「疎」概念は，「禁句を持つ」という位相的な「疎」概念と一致するという理論的に良い性質がある．
∗ (L) = 0 であることと，L は禁句を持つことは同値．
定理 11 ([20]). 正則言語 L について，δA

5

2.3

可測性

定義 12 (内密度，外密度，可測性). C, D を言語クラスとする．A 上の言語 L に対する (A 上の)C
内密度を∗∗(K) | K ⊆ L, K ∈ CA , δA(K) 6= ⊥}µC (L) = sup{δAA

で定義し，(A 上の)C 外密度を∗∗(K) | L ⊆ K, K ∈ CA , δA(K) 6= ⊥}µCA (L) = inf{δAで定義する．L が (A 上)C 可測であるとは，µCA (L) = µC (L) が成り立つことを言い，このときAµCA (L) を µCA (L) で表し L の (A 上の)C 測度と呼ぶ．D が C 可測であるとは，各アルファベット A
に対して DA に属する全ての言語が A 上 C 可測であることを言う．
注意 13. CA が空集合と A∗ を含む場合は上記定義の inf および sup の右辺の集合は常に非空であり
0 ≤ µC (L) ≤ µCA (L) ≤ 1 が成り立つ．密度と同様に，可測性はアルファベットに依存する (例 33
A
でも改めて説明する)．以降，単に「L が C 可測である」と言った場合には，常に L ⊆ A∗ となる
最小のアルファベット A 上で可測であることを意味することとし，µCA (L), µC (L), µCA (L) を単にAµC (L), µC (L), µC (L) と A を省略して書けることとする．
さらに，以降，本論文では常に全ての言語が密度を持つようなクラスのみについて考える．そのため，単に「言語クラス C 」と言った場合は，「任意の L ∈ C について L は密度を持つ」と暗に仮定する．実際，以降は具体的な C について考察する際には常に C は正則言語のクラス REG かその部
分クラスのみを考える．また，「REG 可測」を「正則可測」と呼ぶこととする．
続く 2.4 節で正則可測・正則非可測なさまざまな言語の例を紹介するが，ここでは一般に「言語L が C 可測である」ことの直感を説明する．言語 L に対してある K ∈ C が存在して K ⊆ L かつ
∗ (L)−δ ∗ (K) = 0 となる場合に「L は C で内側から零近似可能」と呼ぶ．同様に，δ ∗ (M )−δ ∗ (L) = 0
δA
AA
A
なる L ⊆ M ∈ C が存在するときに「L は C で外側から零近似可能」と呼ぶ．K ⊆ L ⊆ M であれば
∗ (K) ≤ µ (L) ≤ µ (L) ≤ δ ∗ (M ) であるから，上のように L が C で内外から (K と M
定義より δA
CA
C∗ (K) = µ (L) = µ (L) = δ ∗ (M ) となり L は C 可測となる．
で) 零近似可能である場合は δACAC
しかし，L が内外から C で 零近似可能 でない場合でも C 可測になる場合があり (続く 2.4 でそのような例を説明する)，C 可測性の議論ではどちらかというとこちらの場合が重要になるため，用語を導入∗ (L)−δ ∗ (K ) = 0 とする．言語 L と言語の列 (Kn )n について (1) 各 n ∈ N で Kn ⊆ L (2) limn→∞ δAnA
なる場合「列 (Kn )n は内側から L に収束する」と言う．条件 (1) の包含関係を逆 (各 n ∈ N で L ⊆ Kn )にすることで「列 (Kn )n は外側から M に収束する」も同様に定義できる．C の言語の列 (Kn )n で∗ (K ) = δ ∗ (L) が
L に内側から収束するような列が存在する場合は，定義より µC (L) = limn→∞ δAnA成り立つ．同様に，C の言語の列 (Mn )n で L に外側から収束するような列が存在する場合は，定義∗ (M ) = δ ∗ (L) が成り立つ．そのため L に内側・外側から収束する C の言より µC (L) = limn→∞ δAnA
語の列 (Kn )n , (Mn )n が存在する場合は µC (L) = µC (L) となり L は C 可測となる．このとき，C の言語の対の列 (Kn , Ln )n は L に両側から収束すると言う．実際，L が C 可測であることと，L に両側から収束する C の言語の対の列が存在することは等価である．内外測度の基本的な性質を述べた
以下の補題は次節で用いる．
補題 14 ([21]). C を補集合に閉じた言語クラスとする．このとき言語 L が C 可測であることと，µC (L) + µC (L) = 1 が成り立つことは同値である．
補題 15 ([21]). クラス C と言語 K, L について次が成り立つ：∗ (L) 6= ⊥ ならば µ (L) ≤ δ ∗ (L) ≤ µ (L)．L が C 可測ならば µ (L) = δ ∗ (L) = µ (L)．
(不等式) δA
C
C
A
A
C
C

(単調性) K ⊆ L ならば µC (K) ≤ µC (L)．
6

(劣加法性) C が和集合について閉じてるならば µC (K ∪ L) ≤ µC (K) + µC (L)．
µC (L) − µC (L) の値は 0 から 1 の間の実数値であり，直感的には言語 L の「C での近似しにくさ」を表していると考えて良い．この値 µC (L) − µC (L) を L の C ギャップと呼ぶ．L の C ギャップが 0であるとは L が可測ということであり，逆に C ギャップが 1 となる場合は L が C によって内側からも外側からも密度の意味で「全く近似できない」という状況を表す．

2.4

正則可測・正則非可測な言語の例

定理 16 ([21]). 以下の文脈自由言語は，全て正則言語ではないが，全て正則可測：

1. D = {w ∈ {a, b}∗ | |w|a = |w|b かつ任意の uv = w について |u|a ≥ |u|b }.
2. B = {w ∈ {a, b}∗ | |w|a = |w|b }.
3. P = {w ∈ {a, b}∗ | w は左から読んでも右から読んでも同じ語 (すなわち回文)}.
4. O3 = {w ∈ {a, b, c}∗ | |w|a = |w|b または |w|a = |w|c }.
5. O4 = {w ∈ {x, x, y, y}∗ | |w|x = |w|x または |w|y = |w|y }.
6. G = {an1 ban2 b · · · ank b | k ≥ 1 で各 1 ≤ i ≤ k に対して ni 6= i}.
7. K = S1 {c}A∗ ∪ S2 {c}A∗ ，ここで A = {a, b, c} で S1 と S2 はそれぞれ
S1 = {a}{bi ai | i ≥ 1}∗

S2 = {ai b2i | i ≥ 1}∗ {a}+と定義されている．
補足 17. 定理 16 中に表れる言語は全て文脈自由言語であるが，いずれも正則言語ではない．D, B, P
は典型的な非正則言語の例としてよく知られているが，それ以外の言語についてその複雑性を簡単に説明する．
O3 と O4 は Flajolet [12] によって本質的に曖昧4 な文脈自由言語であることが示されており，文脈自由言語の中でも比較的複雑な構造を持つ．
古典的な Chomsky–Schützenberger の定理 [6] は，もし文脈自由言語 L が無曖昧ならば，次で定義される級数∞X
FL (z) =#(L ∩ An ) z nn=0すなわち L の母関数が代数関数となることを述べている．よって L の母関数が超越関数となるなら
ば，L は本質的に曖昧となるが，Flajolet は O4 の母関数が超越関数である [12] こと，G の母関数が超越関数である [13] ことをそれぞれ示している．
最後に，Kemp [15] によって定義された言語 K の複雑さについて説明する．言語の密度はもともと代数的符号理論 (cf. [4]) などの文脈で Berstel らによって考察がなされていたが，Berstel は彼の 1973 年の論文 [2] にて任意の無曖昧文脈自由言語の密度が代数的数となることを示した．[2] 以降，密度が超越数であるような文脈自由言語が存在するかどうかは未解決であったが，1980 年にKemp [15] がそのような言語を実際に構成した．それが定理 16 の K である．
このように，G や K は形式言語理論的な視点 (本質的に曖昧) からも組合せ論的な視点 (母関数・密度がそれぞれ超越的) からも複雑な文脈自由言語であり，それにも関わらず正則言語でいくらでも近似ができるということを定理 16 は言っている．

4

文脈自由言語 L が無曖昧 (unambiguous) であるとは，L を生成する無曖昧な文脈自由文法が存在することを言う．
文脈自由言語が本質的に曖昧とは，それを生成する無曖昧な文法が存在しないことを言う．文法が無曖昧であるとは，任意の語 w についてその文法において w を生成する最左導出列がたかだか１つであることを言う．無曖昧な文脈自由言語の詳細は文献 [23] の 3 節を参照されよ．

7

Proof. 定理 16 の証明は全て [21] に書かれているが，可測性の良い例題となるため，半 Dyck 言語 Dが正則可測であることの証明の概略をここに記す．A = {a, b} とする．まず，例 5 で述べたように
D の密度は 0 であるため，∅ で内側から自明に零近似できる．しかし，D は正則言語で外側から零近似できない．なぜなら，定理 11 より正則言語 L の密度が 0 であれば禁句を含むためある w ∈ A∗
で L ∩ A∗ wA∗ = ∅ となる．しかし，例 5 で説明したように D は禁句を持たない (稠密である)．よって D ∩ A∗ wA∗ 6= ∅ となり D ⊊ L であるため L は D の外側からの零近似にはなりえない．
よって D が正則可測であることを示すためには，D に外側から収束する正則言語の列を構成する必要がある．各 k ≥ 1 に対して Lk = {w ∈ {a, b}∗ | |w|a = |w|b mod k} と定義する．Lk は k 状態の決定性オートマトンで認識できるため，正則言語であり，特に D ⊆ Lk が各 k について成り立つ．
簡単な解析から Lk の密度が 1/k となることが示せ，よって正則言語の列 (Lk )k≥1 は D に外側から収束する．
また，次の言語 L2n は文脈依存言語ではあるが，文脈自由言語ではない．この言語も正則可測である．
定理 18. 言語 L2n = {a2 ∈ {a}∗ | n ∈ N} は正則可測である．
n∗ (L n ) = 0 が成り立つため，外側から収束する正則言語の列を構成すれProof. A = {a} とする．δA
2∗ (L ) = 1/k が成ば良い．Lk = (ak )∗ ∪ {an | 0 < n < k} は正則言語であり，各 k ≥ 1 に対して δAk∗ (L ) = 0 である．任意の k ≥ 1 と n ∈ N について，a2n ∈ L
り立ち，特に limk→∞ δAk
2k すなわちnkn
L2n ⊆ L2k であることを示す．2 < 2 ならば定義より明らかに L2k に属するので，2 ≥ 2k の場合
nkkを考えればよいが，2n = 2k · 2n−k であるため a2 は a2 の 2n−k ∈ N 回の繰り返しとなり (a2 )∗ に属する．よって正則言語の列 (L2k )k≥1 は L2n に外側から収束する．
∗ (L) = α となる正則可測な言語 L が存在することがさらに，任意の実数 0 ≤ α ≤ 1 に対して，δA示せる．
∗ (L) = α となる正則定理 19. A が２つ以上の文字を含む場合，任意の実数 0 ≤ α ≤ 1 に対して δA
可測な言語 L が存在する．

Proof. A = {a, b} の場合について考える (一般の場合も同様に示せる)．実数 α ∈ [0, 1] の 2 進数展開を考えると∞X
α=αn 2−nn=1となる列 (αn )n≥1 (ただし各 i で αi ∈ {0, 1}) が存在する．K0 = ∅, M0 = A∗ として，各 n ≥ 1 について正則言語 Kn , Mn を以下のように定義する：
M
bn−1 aA∗ ∪ K
αn = 1n−1n−1 αn = 1
Mn =
Kn =
Mn−1 \ bn−1 aA∗ αn = 0Kn−1αn = 0
各 n, m ≥ 1 に対して n 6= m ならば bn−1 aA∗ ∩ bm−1 aA∗ = ∅ のため，構成から任意の n ∈ N で∗ (bn−1 aA∗ ) = 2−n が成Kn ⊆ Mn が成り立つ．密度の連接の性質 (補題 4) から各 n ≥ 1 に対して δAり立つ．また，密度の加法性および差集合の性質 (補題 4) より各 n ≥ 1 に対してそれぞれ∗
δA(Kn ) =nX

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

i=1
i=1
∗
∗
∗ (L) = α となが成り立つ．よって limn→∞ δA (Kn ) = δA (Mn ) = α となり，(Kn , Mn )n は密度が δAる言語 L =Sn∈N Kn =T

n∈N Mn に両側から収束する．

8このように，多くの複雑な言語が正則可測であり，さらに正則可測な言語は非可算無限個存在す
る一方，次の言語は正則非可測である．
定理 20 ([21]). A = {a, b} 上の以下の言語は全て正則非可測：

1. 各 n ≥ 1 について Mn = {w ∈ A∗ | |w|a > n · |w|b }．
2. 原始語全体の集合 Q．ここで w が原始語 (primitive word) であるとは，w が非空であり，自分よりも短い語の繰り返しとならない (v n = w ⇒ v = w かつ n = 1) ことを言う．
特に，Q と n ≥ 2 の場合の Mn はそれぞれ正則ギャップが 1 となり，強い意味で正則非可測である．
補足 21. M1 は「a の個数が b の個数よりも多い {a, b} 上の文字列全体」であり，これが正則言語に
よって「近似できない」ことは最初に Eismann–Ravikumar [11] によって証明された．著者は [21]において Eismann–Ravikumar の証明を単純化し，さらに n ≥ 2 の場合においても Mn が正則非可測であることを示した．各 n ≥ 1 について Mn は決定性プッシュダウンオートマトンで受理できる
ため，決定的な文脈自由言語である．
原始語の集合 Q は語の組合せ論や文字列アルゴリズムにおいて非常に重要な対象であるが「Q は文脈自由ではない」という Dömösi–Horváth–Ito 予想 [9] は 30 年来の未解決問題である (この予想に関するこれまでの既存研究は書籍 [7] で網羅的にまとめられている)．著者はこの予想を肯定的に解決するために「任意の文脈自由言語の正則ギャップは 1 未満である一方，Q の正則ギャップは 1になるのではないか」と言う予想を立てた．Q の正則ギャップが 1 になることは示せたが，その後
Mn (n ≥ 2) という反例 (文脈自由言語ながら正則ギャップが 1) を見つけたというのが [21] の研究背景である．
「Q は CFL 非可測である ([21])」(よって Q は文脈自由ではない) と著者は予想しているが，こちらはまだ証明も反証もされていない．

3

可測な言語族の一般的な性質

前節では正則可測・非可測な言語の具体例をいくつか見てきた．本節では可測な言語族の一般的な性質，すなわち可測な言語全体のクラスの閉包性，および正則可測性の決定不能性について議論する．最後に，Carathéodory 条件による可測性の特徴づけも与える．
定理 22. C を Bool 演算に閉じている言語クラスとする．L, K がそれぞれ C 可測であり，L, K とC の言語から有限回の Bool 演算の適用で構成される言語が密度を持つならば，補集合 L，和集合
L ∪ K および積集合 L ∩ K もそれぞれ C 可測である．

Proof. C は補集合に閉じているため，補題 14 より L が C 可測であることと L が C 可測であることは同値である．よって L と K が C 可測のときに L ∪ K が C 可測であることを示せば十分である．
L と K にそれぞれ内側から収束する C の列 (Ln )n , (Kn )n をそれぞれ固定する．C は和集合に閉じているため (Ln ∪ Kn )n は C の列となるがこれが内側から L ∪ K に収束することを示そう．任意の∗ (L) − δ ∗ (L ), δ ∗ (K) − δ ∗ (K ) < ϵ/2 が成ϵ/2 > 0 についてある δ が存在して δ < n なる n では δA
n
n
A
A
A
り立つため，特に密度の差集合の性質 (補題 4) から
∗
∗
∗
∗
∗
∗
(δA
(L) − δA
(Ln )) + (δA(K) − δA(Kn )) = δA
(L \ Ln ) + δA
(K \ Kn ) < ϵ(4)が成り立つ．仮定より (L \ Ln ) ∪ (K \ Kn ) は密度を持つため，密度の劣加法性 (補題 4) から∗∗∗
δA((L \ Ln ) ∪ (K \ Kn )) ≤ δA
(L \ Ln ) + δA
(K \ Kn ) < ϵ(5)∗ ((L ∪ K) \ (L ∪ K )) < ϵ となが得られる．(L ∪ K) \ (Ln ∪ Kn ) ⊆ (L \ Ln ) ∪ (K \ Kn ) のため δAnnり，すなわち列 (Ln ∪ Kn ) が内側から L ∪ K に収束すること言っている．同様にして外側からの収束列も構成できるため L ∪ K は C 可測である．

9

定理 23. C を左商 (または右商) に閉じている言語クラスとする．L が C 可測であり，L の左商
a−1 L(または右商 La−1 ) が密度を持つのであれば C 可測である．

Proof. A 上の言語 L が C 可測として a−1 L も可測であることを示す (右商も同様に示せる)．定義より L に両側から収束する C の言語の対列 (Kn , Mn )n が存在するが，このとき (a−1 Kn , a−1 Mn )n がa−1 L に両側から収束することを示す．
簡単のために A = {a, b} とする (一般の場合でも同様に示せる)．まず，各 a ∈ A に対して L∩aA∗ =aa−1 L が成り立つため，L = aa−1 L ∪ bb−1 L ∪ (L ∩ {ε}) と書くことができる．仮定から aa−1 L とbb−1 L は密度を持ち，さらに共通部分を持たないため密度の加法性 (補題 4) から∗∗∗
δA(L) = δA(aa−1 L) + δA
(bb−1 L)(6)

∗ (a−1 K ) ≤が成り立つ．定義より各 n に対して Kn ⊆ L となるため，a−1 Kn ⊆ a−1 L となり，特に δAn∗ (a−1 L) であることがわかる．(K ) は L に内側から収束するため，任意の ϵ/2 > 0 に対してあδAn n∗ (L) − δ ∗ (K ) < ϵ/2 となるが，このとき，式 (6) より同時にる δ が存在して δ < n となる n では δA
n
A
ϵ
∗
∗
∗
∗
∗
∗
δA
(L) − δA(Kn ) = (δA(aa−1 L) − δA(aa−1 Kn )) + (δA(bb−1 L) − δA
(bb−1 Kn )) <(7)2が成り立つ．密度の連接の性質 (補題 4) より，不等式 (7) は
1 ∗ −11 ∗ −1ϵ∗∗ −1(δA (a L) − δA
(a−1 Kn )) + (δA(b L) − δA(b Kn )) <
2
2
2
∗
−1
∗
−1
と変形でき，ここから各 n > δ について δA (a L) − δA (a Kn ) < ϵ が成り立つことが言え，すな
わち (a−1 Kn )n は a−1 L に内側から収束する列となっている．同様に，(a−1 Mn )n は a−1 L に外側から収束する列となることも示せる．

正則言語によって近似できる言語全体のクラスをExt(REG) = {L ⊆ A∗ | L は A 上正則可測 }A:アルファベットと書くことにする．定理 23 で示した閉包性および定理 20 から，文脈自由言語の正則可測性の決定
不能性は（次の予想を仮定した上で）Greibach のメタ定理 [14]5 を用いることで示せる．なお文脈自由言語の定義は省略するが，必要であれば [23] の 3 節を参照されよ．
予想 24. 文脈自由言語 L ⊆ A∗ が密度を持つならば，その商 a−1 L, La−1 も密度を持つ．
定理 25. 予想 24 が正しければ，与えられた文脈自由文法が正則可測な言語を生成するかどうかは決定不能．

Proof. 文脈自由言語全体のクラスを CFL で表す．CFL は左右からの商に付いて閉じている．また，仮定および定理 23 より正則可測な文脈自由言語全体 P = ExtA (REG) ∩ CFL もまた左右からの商について閉じている．明らかに REG ⊆ P が言え，また定理 20-(1) より正則非可測な文脈自由言語が存在するため P ⊊ CFL である．CFL においては普遍性 (universality: 与えられた文脈自由文法について，その文法が A∗ を生成するかどうか) が決定不能であるため，Greibach のメタ定理 [14]より，与えられた文法が正則可測な文脈自由言語を生成するかどうかも決定不能である．
最後に，C 可測であることの Carathéodory 条件による特徴付けを与える．以下の定理の証明は，形式言語の密度特有の条件も入っているが，議論の骨子は通常の測度論における Lebesgue 可測性の Carathéodory 条件による特徴付けと同様である (cf. [22] の定理 5.1 の証明 (p.81))．

紙面の都合上正確な言明は省略するが，Greibach のメタ定理は「(CFL のような) ある程度の複雑さを持つ言語族 Cにおいて，任意の正則言語で成立する性質 P がある L ∈ C において成立しない場合，与えられた C の言語 (の記述) が性質 P を満たすかどうかは決定不能」であることを言っている．
510

定理 26. Bool 演算に閉じたクラス C と言語 L ⊆ A∗ について考える．L および C の言語に対して有限回 Bool 演算を適用して得られる任意の言語が密度を持つ場合，L が C 可測であることと次のCarathéodory 条件は同値：∀X ⊆ A∗µC (X) = µC (X ∩ L) + µC (X ∩ L).

(8)

Proof. L が Carathéodory 条件 (8) を満たせば，特に X = A∗ と置くことで µC (A∗ ) = 1 = µC (L) +µC (L) となり，C は補集合に閉じているため補題 14 より L は C 可測であることが直ちに得られる．
L が C 可測であると仮定して Carathéodory 条件 (8) を満たすことを示す．任意の X ⊆ A∗ につ∗ (K) ≤ µ (X) + ϵ が成り立つ K ∈ C
いて，µC の定義より任意の ϵ > 0 に対して X ⊆ K かつ δACが存在する．L および K, K ∈ C はそれぞれ C 可測であり，仮定より Bool 演算 K ∩ L と K ∩ L はそれぞれ密度を持つため，定理 22 よりそれぞれ C 可測でもある．K = (K ∩ L) ∪ (K ∩ L) かつ(K ∩ L) ∩ (K ∩ L) = ∅ のため密度の加法性 (補題 4) より∗∗∗
δA(K) = δA
(K ∩ L) + δA(K ∩ L)(9)∗∗∗µC (X) ≥ δA(K) − ϵ = δA(K ∩ L) + δA(K ∩ L) − ϵ(10)が得られる．よって，≥ µC (X ∩ L) + µC (X ∩ L) − ϵ(11)となり，ϵ > 0 は任意に取っていたため最終的にµC (X) ≥ µC (X ∩ L) + µC (X ∩ L)

(12)が得られる．逆向きの不等式は µC の劣加法性 (補題 15) から直ちに言える．

4

正則言語の局所多様体と可測性

本節では，局所多様体と呼ばれる良い閉包性を持った正則言語のいくつかの部分クラスについて，その可測性を明らかにしていく．正則言語の局所多様体の定義や，その有限モノイドとの対応(Eilenberg 型の定理) の説明には代数的言語理論の基礎知識が不可欠のため，続く 4.1 節で簡単に
入門する．

4.1

代数的言語理論の基礎と Eilenberg の多様体定理

代数的言語理論では，まず A∗ を連接 · を二項演算として持った代数構造 (ε を単位元とした自由モノイド) とみなし各概念を定義していく．言語 L ⊆ A∗ について，その統語的合同関係 (syntactic
congruence) ≡L はv ≡L w ⇔ ∀x, y ∈ A∗ (xvy ∈ L と xwy ∈ L は同値)と定義される A∗ 上の二項関係であり，これは A∗ 上の合同関係 (同値関係かつ u ≡L w ⇒ ∀x, y ∈A∗ (xuy ≡L xwy)) となる．L ⊆ A∗ の統語モノイド (syntactic monoid)Synt(L) とは自由モノイドA∗ をこの合同関係 ≡L で割ったモノイド Synt(L) = A∗ / ≡L である．Synt(L) は A∗ を割ったモノ
イドであるため，自然な全射準同型 ηL : A∗ → Synt(L) が導出されるが，これを L の統語準同型(syntactic morphism) と呼ぶ．定義より，任意の言語 L について L = ηL−1 (ηL (L)) が成り立つ．
例 27. A = {a} として言語 L = (aa)∗ について考える．２つの自然数 n, m の偶奇が等しい (n = m
mod 2) とき，任意の x, y ∈ A∗ について語 xan y と語 xam y の長さの偶奇は等しいため，それらがL に属するのは同値である．よって an ≡L am が成り立つ．逆に，n, m の偶奇が異なるのであれば，
an か am の偶数長の方だけが L に属するため an 6≡L am となる．よって L の統語モノイドは位数 2の群と同型 Synt((aa)∗ ) ∼= Z/2Z となる．

11

次に，A = {a, b} として半 Dyck 言語 D ⊆ A∗ について考える．語 w 中に表れる括弧の整合的な対応を意味する ab という部分語を全て消して得られる語を Trim(w) として表す．例えば Trim(aabb) = abであり Trim(b ab ab a) = ba となる．簡単な考察から，任意の語 w についてその不動点 Trim∗ (w) が一意に定まり Trim∗ (w) = bm an (m, n ∈ N) という形となることが分かる (a のあとに b が来ればそれは Trim によって消されるので，不動点は a のあとに b は来ない)．w ∈ D と Trim∗ (w) = ε は同値であり，実際，括弧の対応の整合性が取れているかどうかは Trim∗ (w) のみが重要であり，特にu ≡D v ⇔ Trim∗ (u) = Trim∗ (v) が成り立つ．よって Synt(D) は 2 元 p, q で生成され pq = 1 という関係のみを満たすモノイド B = h{p, q} | pq = 1i (これは bicyclic モノイドと呼ばれる) と同型となる．
このとき統語準同型 ηD : A∗ → B は Trim∗ (w) = bm an となる各 w ∈ A∗ に対して ηD (w) = q m pn と
−1
写し，B の単位元 1 について ηD(1) = D が成り立つ．モノイド B においては (m, n) 6= (m′ , n′ ) な′′
らば q m pn 6= q m pn のため，特に B は無限モノイドである．
最後に，回文全体の集合 P = {ε, a, b, aa, bb, aaa, aba, · · · } について考える．このとき実は u ≡Pv ⇔ u = v であることが示せ，統語モノイドは A∗ そのものとなる．このように統語的合同関係が自明な恒等関係になる言語は分離的 (disjunctive) と呼ばれ，分離的な言語の統語モノイド (すなわ
ち自由モノイド) には代数的な情報はなにもない．
例 27 で見たように，言語によっては統語モノイドは有限になったり無限になったりするが，以下の定理は正則言語の場合は必ず有限になりまたその逆も成り立つことを言っている代数的言語理論の基本的な定理である．
定理 28 (Myhill-Nerode [16]). 任意の言語 L ⊆ A∗ について，L が正則であることと，Synt(L) が有限であることは同値．
ある有限モノイド M に対して，一般に M ∼= Synt(L) となるような正則言語 L は多数存在する(例えば Synt((aa)∗ ) = Synt(a(aa)∗ ) ∼Z/2Z
，より一般に言語
L とその補集合 L の統語モノイドは=−1等しい)．逆に，ある言語 L に対して L = η (S) を満たすような準同型 η : A∗ → M と部分集合
S ⊆ M を持つ有限モノイドは多数ある．このように，有限モノイド全体と正則言語全体の間には多対多の関係があるが，「ある種の良い閉包性を満たす正則言語のクラス全体」と「ある種の良い閉包性を満たす有限モノイドの族全体」には綺麗な１対１が存在することが知られている．
定義 29 (正則言語の多様体). 正則言語のクラス C ⊆ REG が次の３つの閉包性を満たすとき，C を多様体 (variety) と呼ぶ．

(L1) C は Bool 演算に閉じている (L, M ∈ C ⇒ L, L ∪ M, L ∩ M ∈ C)．
(L2) C は左右からの商に閉じている (L ∈ C, a ∈ A ⇒ a−1 L, La−1 ∈ C)．
(L3) C はモノイド準同型の逆像に閉じている (L ∈ CA , h : B ∗ → A∗ ⇒ h−1 (L) ∈ CB )．
定義 30 (有限モノイドの多様体). 有限モノイドの族 V ⊆ Mon が次の３つの閉包性を満たすとき，V を多様体 (pseudovariety) と呼ぶ．

(M1) 除モノイド (divisor) を取る操作について閉じている．ここでモノイド M が N の除モノイドであるとは，ある準同型 h : N → M と N の部分モノイド N ′ が存在して h(N ′ ) = M が成り立つことを言う．
(M2) 有限直積に閉じている (M1 , . . . , Mn ∈ V ⇒ M1 × · · · × Mn ∈ V).
有限モノイドの族 V ⊆ Mon を含む最小の多様体を hVi で表す (多様体の積集合も多様体になるため，
hVi は常に一意に存在する)．

12

定理 31 (Eilenberg の多様体定理 [10]). 正則言語の多様体全体と有限モノイドの多様体全体は一対一に対応する．より精確に，正則言語の多様体 C ⊆ REG および有限モノイドの多様体 V ⊆ Mon に対する写像

F (C) = h{Synt(L) | A は文字集合, L ∈ CA }i G(V) = {L ⊆ A∗ | Synt(L) ∈ V}A:有限アルファベット
がそれぞれ正則言語の多様体と有限モノイドの多様体間の全単射となっており，さらに互いに逆写像となっている．
正則言語全体 REGA は自明な多様体の例であり，これに対応する有限モノイドの多様体は有限モノイド全体 Mon である．歴史的には，非常に多くの非自明な正則言語の多様体と有限モノイドの多様体が発見されており (cf. [17, 8])，その中でも古典かつ有名な例は次の星無し言語と非周期的な有限モノイドの対応であろう．ここで，モノイド M が非周期的 (aperiodic) であるとは，任意のm ∈ M に対してある n ≥ 1 が存在して mn = mn+1 が成り立つことを言う．
定理 32 (Schützenberger の定理 [19]). 星無し言語の多様体 SF と非周期的な有限モノイドの多様体
Ap が対応する．すなわち L ∈ SF ⇔ Synt(L) ∈ Ap が成り立つ．
例 2 で (aa)∗ ⊆ {a}∗ が星無し言語でないことを証明無しで言及したが，上の Schützenberger の定理を使えば即座に示すことができる：(aa)∗ の統語モノイドは位数 2 の群 Z/2Z であり，単位元ではない元 x ∈ Z/2Z について xn 6= xn+1 が任意の n ≥ 1 で成り立つため周期的である．
次項からは密度・可測性で定義されるような正則言語の部分族についての考察を展開していくが，一般に，密度や可測性は準同型の逆像について閉じていない．そのため「密度が 0 か 1 となる正則言語全体」のクラス ZO は多様体とはならない．
例 33. L を A 上の正則可測でない言語とする．A に新たな文字 c ∈/ A を加えたアルファベット∗
B = A ∪ {c} を考えると，L を B 上の言語と考えると A は c を禁句として持つため無限の猿定理∗ (A∗ ) = 0 であり，よって L ⊆ B ∗ の密度は B 上で 0 となり，L は正則言語の定数列 (∅, A∗ )より δBnで明らかに近似できる．そのため L は B においては可測であるが，A∗ から B ∗ への包含準同型
h : A∗ → B ∗ の逆像 L = h−1 (L) は A 上の言語で仮定より可測ではない (よって密度も持たない)．
そのため，密度や可測性は準同型の逆像によって保存されない性質であることがわかる．一般に，密度や可測性などの言語の母関数に立脚した概念は準同型の像や逆像と相性が悪い (大抵の場合は保存されない)．
しかし，ZO は準同型の逆像に閉じていないだけで次の意味で多様体を一般化した概念の具体例となっており，さらに一般化された多様体概念でも Eilenberg 型の定理が成り立つことが知られている．
定義 34 (正則言語の局所多様体). 正則言語の族 C ⊆ REGA が定義 29 の２つの閉包性 (L1) と (L2)を満たすとき， C を A 上の局所多様体 (local variety) と呼ぶ．
定義 35 (有限モノイドの局所多様体). アルファベット A で生成される有限モノイドの族 V ⊆ Mon
が次の閉包性を満たすとき，V を A 上の局所多様体 (local pseudovariety) と呼ぶ．

(M’1) 準同型の像を取る操作について閉じている．
(M’2) 部分直積 (subdirect product) に閉じている．すなわち M1 , . . . , Mn ∈ V ならば，その直積
M1 × · · · × Mn の部分モノイド M が「各 1 ≤ i ≤ n から自然に誘導される射影 pi : M → Miが全て全射」という性質を満たすならば M ∈ V．
定理 36 (局所多様体版の Eilenberg 型定理 [1]). 正則言語の局所多様体全体と有限モノイドの局所多様体全体は一対一に対応する．

13

局所多様体は、言語クラスとなる多様体とは異なり、固定されたアルファベット A 上の言語族に対する概念である．A 上の正則言語全体 REGA が局所多様体であることは，REG が多様体である
ことから明らかであるが，2 節で導入した言語族 FIN と ZO も次で説明するように局所多様体となっており，次項から FIN, ZO, SF のそれぞれの可測性について中心的に議論を行う．
例 37. 有限または補有限な言語全体のクラスを FIN とし，冪零な有限モノイドの全体を Nil とする．ただしモノイド M が冪零 (nilpotent) であるとは，ある元 z ∈ M が存在して任意の m ∈ M に対して z · m = m · z = z が成り立ち (この様な元 z を零元と呼ぶ)，任意の m に対してある i ≥ 1 で
mi = z となることを言う．FIN と Nil はそれぞれ正則言語と有限モノイドの局所多様体となっている．さらに，FIN と Nil が対応する．すなわち L ∈ FIN ⇔ Synt(L) ∈ Nil．
例 38 ([20]). 密度が 0 か 1 の正則言語全体のクラスを ZO とし，零元を持つ有限モノイド全体をZ とする．ZO と Z はそれぞれ局所多様体となっている．さらに，ZO と Z が対応する．すなわち，
L ∈ ZO ⇔ Synt(L) ∈ Z．

4.2

局所多様体の閉包作用素としての Carathéodory 拡張∗

定理 39. アルファベット A 上の言語族 C ⊆ 2A を C 可測な言語全体へ写す以下の写像

ExtA (C) = {L ⊆ A∗ | L は A 上 C 可測 }∗は，A 上の言語族の閉包作用素となっている．すなわち，C, D ⊆ 2A について以下を満たす：
拡大的： C ⊆ ExtA (C)．
単調的： C ⊆ D ならば ExtA (C) ⊆ ExtA (D)．
冪等的： ExtA (ExtA (C)) = ExtA (C)．

Proof. 拡大的・単調的であることは定義より明らかであるため，冪等的であることを示す．L ∈ExtA (ExtA (C)) について考える．定義より L に両側から収束するような ExtA (C) に属す言語の対列 (Kn , Mn )n が存在する．各 n に対して Kn , Mn はそれぞれ ExtA (C) に属するため，Kn に内側から収束する C の列 (K(n,i) )i と Mn に外側から収束する C の列 (M(n,i) )i が存在する．このとき，(K(n,n) , M(n,n) )n は L に両側から収束する C の対列となっているため L ∈ ExtA (C) が成り立つ．
また，任意の正則言語は密度を持ち (系 9)，さらに正則言語全体は Bool 演算と左右からの商について閉じているため，局所多様体の定義と定理 22–23 から次の系が得られる．
系 40. 正則言語の局所多様体 C ⊆ REGA について，ExtA (C) ∩ REGA も局所多様体である．

1 節で提起したとおり，拡張 ExtA (REG)(または ExtA (REG) ∩ CFL) の性質を明らかにしたい．
しかし，2.3 節で説明したとおり，ExtA (REG) は非常に複雑な言語も含んでおり，また CFL は理論的に明らかになっていない点が多く，これは現時点で難しい問題と思われる．
本節では以降，ExtA (REG) や ExtA (REG) ∩ CFL のある種の「ミニチュア」である ExtA (ZO) ∩REG や ExtA (SF)∩REG について考察する．以降，拡張の像を正則言語に制限した写像を RExtA (C) =ExtA (C) ∩ REGA で表す．
定義より，密度が 0 (あるいは 1) な言語の列 (Ln )n で近似できるような言語は同じく密度が 0(あるいは 1) な言語に限る．よって次の定理が成り立つ (ExtA (ZOA ) は非正則な言語も含むため
ZOA ⊊ ExtA (ZOA ) となることに注意)．また，似たような議論で有限・補有限な局所多様体 FINAについても，RExtA は拡張しないことが示せる．
定理 41. 任意の A について，RExtA (ZOA ) = ZOA ．
定理 42. 任意の A について，RExtA (FINA ) = FINA ．

14

また，アルファベットが単元集合からなる場合は，SFA = FINA が成り立つことが知られている
ため，次の系が得られる．
系 43. アルファベット A = {a} においては ExtA (SFA ) = SFA = FINA が成り立つ．
しかし，アルファベットが単元集合でない場合は事情が異なってくる．
定理 44. 2 つ以上の文字を含む A において，RExtA (SFA ) ⊋ SFA ．

Proof. 前項で説明したとおり (aa)∗ ∈/ SFA であるため，(aa)∗ ∈ RExtA (SFA ) であることを示す．
A は 2 つ以上の文字を含むため，(aa)∗ ⊆ a∗ = A∗ \ A∗ (A \ {a})A∗ の密度は共に 0 となり，したがって星無し言語の対の定数列 (∅, a∗ )n が (aa)∗ に両側から収束する．
∗ (L) > 0 ならば L は奇数長の語
定理 45. アルファベット A 上の星無し言語 L ∈ SFA について，δAも偶数長の語も両方含む．

Proof. ηL : A∗ → Synt(L) を L の統語準同型とし，ηL (L) = S ⊆ Synt(L) と置く．L は正則言語であるため Synt(L) は有限である．モノイド M の空でない部分集合 I 6= ∅ が M IM = {abc | a, c ∈M, b ∈ I} ⊆ I を満たすとき I をイデアルという．イデアル I と J の積 IJ ⊆ I ∩ J もまたイデアルになるため，イデアル全体の積は M が有限な場合は (包含関係で) 最小なイデアルとなる (M が無限の場合は全体の積が空集合になり得る)．Synt(L) の最小イデアルを K と置き，k ∈ K の逆像と−1(k) と置く (ηL は全射なので必ずそのような語が存在する)．
なる語をそれぞれ wk ∈ ηL∗
このとき，δA (L) > 0 という仮定から S ∩ K 6= ∅ が言える．なぜなら，K に属さない任意の元m ∈ Synt(L) \ K および任意の文字列 x, y ∈ A∗ について，ηL (xwk y) = ηL (x) · k · ηL (y) ∈ K のた
−1(m) が wk を禁句に持つことを意味
め特に ηL (xwk y) 6= m となるからである．これはすなわち ηL−1
しており，よって無限の猿定理より ηL (m) の密度は 0 となる．密度が 0 な言語の有限個の和集合∗ (η −1 (K)) = 1 が成り立つ．そのため，L の密度が非零であるためにはやはり密度 0 であるため，δA
L
は S が少なくとも１つ K の元を含んでいる必要がある．その様な元 t ∈ S ∩ K を１つ固定する．
∗ (η −1 (K)) = 1 であるため，特に η −1 (K) はある奇数長の語 w
δA
odd を必ず含む (そうでないとするとL
L
密度が 1/2 以下になってしまう)．wodd の像を modd = ηL (wodd ) とする．このとき，Schützenbergerの定理より Synt(L) は非周期的であるため，ある i ≥ 1 が存在して miodd = mi+1
odd が成り立つ．K はi
最小イデアルであるため，x · modd · y = t となる元 x, y ∈ Synt(L) が存在する (そうでないとするとmodd で生成されるイデアル Synt(L) · modd · Synt(L) が K よりも真に小さいイデアルとなってしま−1(x), wy ∈ ηL−1 (y) をそれぞれ固うため K の最小性に反する)．そのような元 x, y に対して wx ∈ ηL
i w と w w i+1 w は定する．すると２つの語 wx woddyx odd yi+1i
ηL (wx woddwy ) = x · miodd · y = t = x · mi+1
odd · y = ηL (wx wodd wy )i w と w w i+1 w のを満たすため，それぞれ L に属する．wodd の長さは奇数であったため，wx woddyx odd y
長さは偶奇が異なる．よって定理が示された．
言語 (AA)∗ の密度は 1/2 であるが，定理 45 より正測度な星無し言語 L は必ず奇数長の語を含
むため L ⊊ (AA)∗ となり，したがって µSF (AA∗ ) = 0 となり，補集合について考えると同様に
AµSFA (AA∗ ) = 1 が得られる．
系 46. 任意のアルファベット A において (AA)∗ ∈/ ExtA (SFA ). 特に，(AA)∗ の SF ギャップは 1．
定理 44 と系 46 をまとめると，RExtA は SF を非自明な局所多様体に拡張することがわかる：
系 47. ２つ以上の文字を含む A において，SFA ⊊ RExtA (SFA ) ⊊ REGA .
定理 48. A 上の正則言語 L について，以下は同値：

1. L は SFA 可測．
2. Synt(L) の最小イデアルが非自明な部分群を含まない．
15

5

おわりに

本論文では可測性の一般的な性質や，いくつかの局所多様体に対して可測性を明らかにしてきた．
1 節で提起したとおり，拡張 ExtA (REG)(または RExtA (REG) ∩ CFL) の性質を明らかにしたいといのが本研究の基本的な動機である．しかし，現時点では文脈自由言語は明らかになっていない点が多く，ExtA (REG) ∩ CFL の考察は理論的に興味深いものの難しい問題と思われる．例えば予想 24のような基本的な問題も未解決であり，また次の問題も未解決である．無曖昧文脈自由言語に対しては代数関数の理論を使うことで密度を持つことが言えるはず (あるいは folklore) であるが，一般の文脈自由言語については母関数の理論が確立していないため別の道具が必要かもしれない．
問題 49. 任意の文脈自由言語は密度を持つか？
前節では #(A) ≥ 2 の場合，RExtA は SFA を非自明な局所多様体に拡張したが，この局所多様体の特徴づけは今後の課題である．
問題 50. RExtA (SFA ) はどのような局所多様体か？RExtA (SFA ) に対応する有限モノイドの局所多様体は何か？正則言語 L について L ∈ RExtA (SFA ) を決定するアルゴリズムは存在するか？
また，Eilenberg 型の定理 (定理 36) から，A 上の正則言語の局所多様体 C には A 生成有限モノイ
ドの局所多様体 V(C) が，逆に A 生成有限モノイドの局所多様体 V には A 上の正則言語の局所多様体 C(V) が一対一に対応する．よって正則言語の局所多様体上の閉包作用素 RExtA に対応する有限モノイドの局所多様体上の閉包作用素 MExtA : V 7→ V(RExtA (C(V))) が自然に誘導される．
問題 51. 有限モノイドの局所多様体の閉包作用素 MExtA を純代数的に特徴づけられるか？
言語 L が正則可測であるとは直感的には「L が正則言語で任意の精度で近似できる」ということであり，自然な概念である．計算量を下げるために決定問題の厳密解ではなく近似解を求めることはよくあり，正則可測性がそのような場面に理論的・実用的に応用できる可能性もあるかもしれない．また，言語の学習においてはある種の収束概念 (極限同定) を考えるが，これを正則可測性の文
脈での収束に置き換えるとどうなるだろうか．正則可測性の応用は今後の課題であり，本論文を通じて正則可測性を知った読者の方々にもぜひ考えてもらえるとありがたい．
謝辞 丁寧に論文を読んでコメントいただいた PPL2021 の査読者に感謝する．本研究は JSPS 科
研費 JP19K14582 の助成を受けたものである．

16

参考文献
[1] Adámek, J., Milius, S., Myers, R. S. R., and Urbat, H.: Generalized Eilenberg Theorem I: Local Varieties of Languages, Foundations of Software Science and Computation Structures, Muscholl, A.(ed.),Berlin, Heidelberg, Springer Berlin Heidelberg, 2014, pp. 366–380.
[2] Berstel, J.: Sur la densité asymptotique de langages formels, International Colloquium on Automata,
Languages and Programming, France, North-Holland, 1973, pp. 345–358.
[3] Berstel, J. and Perrin, D.: Theory of codes, Pure and Applied Mathematics, Vol. 117, Academic Press
Inc., 1985.
[4] Berstel, J., Perrin, D., and Reutenauer, C.: Codes and Automata, Encyclopedia of Mathematics andits Applications, Cambridge University Press, 2009.
[5] Buck, R. C.: The Measure Theoretic Approach to Density, American Journal of Mathematics, Vol. 68,
No. 4(1946), pp. 560–580.
[6] Chomsky, N. and Schützenberger, M.: The Algebraic Theory of Context-Free Languages*, Computer
Programming and Formal Systems, Vol. 35, Elsevier, 1963, pp. 118–161.
[7] Dömösi, P. and Ito, M.: Context-Free Languages and Primitive Words, World Scientiﬁc Publishing
Company, 2014.
[8] Diekert, V., Gastin, P., and Kuﬂeitner, M.: A Survey on Small Fragments of First-Order Logic over
Finite Words, Int. J. Found. Comput. Sci., Vol. 19, No. 3(2008), pp. 513–548.
[9] Dömösi, P., Horváth, S., and Ito, M.: On the connection between formal languages and primitive
words, 1991, pp. 59–67.
[10] Eilenberg, S. and Tilson, B.: Automata, languages and machines. Volume B, Pure and applied mathematics, Academic Press, New-York, San Franciso, London, 1976.
[11] Eisman, G. and Ravikumar, B.: Approximate Recognition of Non-regular Languages by Finite Automata, Twenty-Eighth Australasian Computer Science Conference (ACSC2005), CRPIT, Vol. 38,
Newcastle, Australia, ACS, 2005, pp. 219–228.
[12] Flajolet, P.: Ambiguity and transcendence, Automata, Languages and Programming, Berlin, Heidelberg, Springer Berlin Heidelberg, 1985, pp. 179–188.
[13] Flajolet, P.: Analytic models and ambiguity of context-free languages, Theoretical Computer Science,Vol. 49, No. 2(1987), pp. 283–309.
[14] Greibach, S. A.: A note on undecidable properties of formal languages, Mathematical systems theory,
Vol. 2(1968), pp. 1–6.
[15] Kemp, R.: A note on the density of inherently ambiguous context-free languages, Acta Informatica,
Vol. 14, No. 3(1980), pp. 295–298.
[16] Myhill, J. R.: Finite Automata and the Representation of Events, Technical Report WADC TR-57624, Wright-Paterson Air Force Base, 1957.
[17] Pin, J.-E.: Mathematical Foundations of Automata Theory, 2012.
[18] Salomaa, A. and Soittola, M.: Automata Theoretic Aspects of Formal Power Series, Springer-Verlag
New York, Inc., Secaucus, NJ, USA, 1978.
[19] Schützenberger, M.-P.: On ﬁnite monoids having only trivial subgroups, Information and Control,Vol. 8, No. 2(1965), pp. 190–194.
[20] Sin’ya, R.: An Automata Theoretic Approach to the Zero-One Law for Regular Languages: Algorithmic and Logical Aspects, Proceedings Sixth International Symposium on Games, Automata, Logics
and Formal Veriﬁcation, GandALF 2015, 2015, pp. 172–185.
[21] Sin’ya, R.: Asymptotic Approximation by Regular Languages, Proceedings of the 47th International
Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM’21), to appear,2021.
[22] 新井仁之: ルベーグ積分講義―ルベーグ積分と面積 0 の不思議な図形たち, 日本評論社, 2003.
[23] 新屋良磨: オートマトン理論再考, コンピュータ ソフトウェア, Vol. 34, No. 3(2017), pp. 3–35.

17