論文紹介： Context-Freeness of Word-MIX Languages #計算機科学

本記事ではDevelopments in Languages Theory 2020 (DLT'20)に採択された論文¹の紹介をしたいと思います．
(残念ながら悪い風邪の影響でDLT'20の現地開催は中止されてしまいました... 開催されていたら人生初の渡米だったのに...)

部分語の個数で定義される言語クラスに対して、正規性・文脈自由性などの問題が決定可能であることを示しました．
単に決定可能と言うだけでなく、言語に対して次元と呼ばれる自然数をうまく定義し、その次元に対する制約で正規性・文脈自由性をきれいに特徴づけています．
本記事では部分語の個数で定義される言語についてはもちろん、正規言語や文脈自由言語についても最初から説明していきたいと思います．

部分語の個数で定義される言語

文字集合(アルファベット)を$A$と書き、$A$の中にある文字を有限個並べて作れる語全体の集合を$A^* $で表します．
長さが0の文字列(空文字列)は $\varepsilon$ と書くことにしましょう．

2つの語$ w,u \in A^* $ に対して $ S(w, u) $ を「$w$中に部分語として現れる$u$の個数」として定義します．
正確には
$$ S(w, u) = |\{ (x,y) \in A^* \mid w = xuy \}| $$ と定義します(ここで$|X|$は集合$X$の濃度を表しています)．
例えば$ababa$中に$ab$は0番目と2番目に2回現れるので$S(ababa, ab) = 2$となります．部分語としての出現は重なってても数えて良いことにしているので$S(aaa, aa) = 2$となります．

さて，与えられた$k$個の語 $w_1, \ldots, w_k \in A^* $について次の言語
$$ L_A(w_1, \ldots, w_k) = \{ w \in A^* \mid S(w, w_1) = S(w, w_2) = \cdots = S(w, w_k) \} $$ が本記事の主役となります．つまり$ L_A(w_1, \ldots, w_k)$は「$w_1, \ldots, w_k$をぴったり同じ個数部分語に含む語」全体の集合です．

呼び名がないと味気ないので$L_A(w_1, \ldots, w_k)$をパラメタ$w_1,\ldots, w_k$で定義される語混合言語(Word-MIX言語)と呼ぶことにしましょう．
名前の由来は，もともと$A = \{a,b,c\}$上の言語
$$ \mathrm{MIX} = L_A(a,b,c) = \{ \varepsilon, abc,acb,bac,bca, cab, cba, aabbcc,\ldots \} $$ と呼ばれる言語が歴史的によく研究されており，語混合言語(Word-MIX)はパラメタを文字から一般の語 $ L_A(w_1, \ldots, w_k) $ に拡張しているからです．
$ \mathrm{MIX} $は(後述する)文脈自由言語でない例としても有名です²．

いくつかの例

$\mathrm{MIX}$のようにパラメタがすべて文字の場合は「無限集合であるか？」などの問題は自明(常に無限集合)ですが，
パラメタを文字から一般の語にすると非自明になってきます．

例えば $ A = \{a,b\}$として$ L_A(ab,ba,a) = \{ \varepsilon, b, bb, bab, bbb, \cdots \}$ は無限集合になりますが(考えてみてください)，
パラメタを1つ追加した$ L_A(ab,ba,a,b) $は有限集合$\{ \varepsilon \}$になってしまいます(考えてみてください)．

こういった状況は、パラメタとなる語同士が出現回数について依存関係を持つからです(例えば任意の語$w$に対して$(S(w, a) \geq S(w,ab))$となります)．
パラメタ語の個数が多くなったり長さが長くなったりするとより非自明度がましていきます．

正規言語と文脈自由言語 (方程式の視点から)

正規言語とは一言で言うと正規表現で記述できる言語のことです．ここで「正規表現」と言っているのは演算として
「連接」「和 |」「Kleeneスター *」の3つの演算のみを許した minimal な正規表現のことです．
プログラミング言語に内蔵されている正規表現で使える「後方参照」などの拡張機能は考えていません．

正規言語の同値な定義として「オートマトンで受理できる言語」というものが有名(Kleeneの定理)ですが，そのわずかな言い換えとして
「左線形方程式の解(最小不動点)になる言語」という別の同値な定義もあります．
左線形方程式とは
$$
X = aX \cup Y \qquad
Y = bY \cup \{ \varepsilon \}
$$
のように有限個の変数(この例では$X$と$Y$)に対する線形($XY$のような項が出てこない)連立方程式のことです．
「左」線形というのは方程式の右辺に現れる項が必ず「$\{\varepsilon\}$」のような有限集合あるいは「$aX$」や「$bY$」のような
変数の左側に文字を連接したものが来ることを表しています．
さてこの左線形方程式$X = aX \cup Y; Y = bY \cup \{ \varepsilon \}$の解はどんな言語でしょうか
(すぐ下で答えを教えますので自力で考えたい方はここでページ送りを止めてください)．

方程式の解を自然に捉える方法として，方程式を帰納的定義だと思う方法があります．
* $X = aX \cup Y$という1つの式を「文字列$w$が$Y$に含まれるなら$w$も$X$に含まれる」「文字列$w$が$X$に含まれるなら$aw$も$X$に含まれる」
* $Y = bY \cup \{\varepsilon\}$というもう1つの式を「文字列$w$が$Y$に含まれるなら$bw$も$Y$に含まれる」「空文字列$\varepsilon$は$Y$に含まれる」(帰納的定義のベースケース)
と考えると，$X$や$Y$の解(最小不動点)は帰納的定義から$X$や$Y$にそれぞれ含まれる文字列全体と考えることができます．
ちなみに$Y$の解は$b^* $，$X$の解は$a^* b^* $ とそれぞれ正規表現で素朴に表すことができます．

さて，一度「方程式の解」として言語を捉える視点を手に入れると，正規言語(左線形方程式の解)の自然な拡張として(左線形とは限らない)一般の「方程式の解となる言語」を考えたくなります．それがまさに文脈自由言語です(その定義から「代数的言語」(algebraic language)とも研究界隈では呼ばれたりします)．

例えば線形ではあるが左線形ではない
$$ P = aPa \cup bPb \cup \{ \varepsilon, a,b \} $$という方程式の解は($ababa$のように)「左から読んでも右から読んでも同じ文字列」すなわち回文全体の集合となります．
回文全体の集合は正規表現では書けない(正規言語ではない)ことも有名です．
さらには次の程式
$$ D = (D) \cup DD \cup \{ \varepsilon \} $$は右辺に$DD$という非線形な項を含む非線形な方程式ですが，こちらの解は
$$ \{\varepsilon, (), (()), ()(), ((())), (())(), ()(()), ()()(),(((()))), \ldots\} $$
といった「開きカッコ"("と閉じカッコ")"の整合性が取れた語」全体となることが(プログラマであれば特に?)容易に推測できるでしょう．
$ D $の解は(semi-)Dyck言語と呼ばれこちらも典型的な非正規言語の例です．

正規言語 = 左線形方程式の解
文脈自由言語 = 方程式の解

という視点から，ある言語$L$が与えられたときに「$L$は正規か？」「$L$は文脈自由か？」という形の問いは，与えられた実数$\alpha$に対して「$\alpha$は有理数か？」「$\alpha$は代数的数か？((ある多項式の根となるか)?)」という形の問いと似ていることがわかります．
これは単なるアナロジーではなく，技術的にも，ある言語$L$が文脈自由言語(の部分クラス)でないことを示すのに，$L$の母関数が代数関数でないことを示すという技法がいろいろな場面で使われています³．

与えられた言語$L$が正規言語か否かを判定する問題(正規性)は，一見簡単な問題に見えますが、それは$L$をどのような表現形式で入力するかに非常に依存する問題です．例えば$L$が一般のチューリングマシン(あるいはプッシュダウンオートマトンでさえも！)で表現されている場合は正規性は決定不能(判定するアルゴリズムが存在しない)です．しかし入力を
$L = L_{\{a,b\}}(a,b) = \{ w \in \{a,b\}^* \mid S(w,a) = S(w,b)\}$のように特定の単純な言語に固定した場合はポンピング補題やMyhill-Nerodeの定理⁴などの技法で非正規性が示せる場合が多いです．
その一方，与えられた言語が文脈自由言語か否かを判定する問題(文脈自由性)は正規性よりはるかに難しく，例えば「原子語の集合は文脈自由か？」という有名な未解決問題があります⁵．

語混合言語の正規性・文脈自由性

前節で見たように、「無限集合であるか？」(無限性)などの問題も語混合言語に対してはなかなかに非自明な問題でした．
一般に正規性・文脈自由性は無限性よりもさらに難しい問題です．
例として、2つのパラメタ語$ab, ba$に対して、アルファベット$A = \{a,b\}$上の語混合言語$L_A(ab,ba)$は正規言語になりますが、$A$に1文字$c$を追加したアルファベット$B = \{a,b,c\}$上では$L_B(ab,ba)$は正規言語ではなくなってしまいます(ちょっと難しいかもしれませんが、意欲のある方は考えてみてください)．正規性や文脈自由性はパラメタ語だけでなく考えるアルファベットにも依存するのです．

パラメタ語が2つであれば語混合言語は必ず文脈自由言語になりますが、パラメタ語が3つ以上になると(例えば$\mathrm{MIX} = L_{\{a,b,c\}}(a,b,c)$のように)語混合言語は一般に文脈自由言語にならない場合もあります．かと言ってパラメタ語が3以上で文脈自由言語になる例もいくらでも存在します．
はたして与えられたパラメタ語で定義される語混合言語の正規性や文脈自由性を決定するアルゴリズムは存在するのでしょうか？

「はい、あります．」というのがDLT'20の論文¹の主結果です．
より具体的には，任意のアルファベット$A$と自然数 $k$および $ w_1, \ldots, w_k \in A^* $ について，次元と呼ばれる自然数$\dim(L_A(w_1, \ldots, w_k))$が計算でき，
1. $ L_A(w_1, \ldots, w_k) $ が正規 $ \Leftrightarrow \dim ( L_A(w_1, \ldots, w_k)) \leq 1 $
2. $ L_A(w_1, \ldots, w_k) $ が文脈自由 $ \Leftrightarrow \dim ( L_A(w_1, \ldots, w_k)) \leq 2 $
であることを示しました⁶.

$\dim(L_A(w_1,\ldots,w_k))$の定義はそれなりにめんどくさいのですが，ざっくり言ってしまうとパラメタ語 $ w_1, \ldots, w_k $ から有限個の有限次元ベクトル空間がアルゴリズミックに構成でき，それらの次元の最大値として定義されます．定義の詳細は論文¹をご参照ください．
さらに $ \dim(L_A(w_1, \ldots, w_k)) $ は計算可能(それを計算するアルゴリズムが存在する)であるため，
「$ L_A(w_1, \ldots, w_k) $ が正規か？」「$ L_A(w_1, \ldots, w_k) $ が文脈自由か？」も上記定理より決定可能となります．嬉しい．

証明の詳細は論文¹を参照してもらうとして、ざっくりまとめると「線形代数20%、組合せ論40%、オートマトン理論40%」という感じの技術構成になっています．
de Bruijn グラフと呼ばれる特殊な形をしたグラフが大活躍します．
「次元が1以下ならば正規」という方向の証明は実際にオートマトンを構成するのですが、その構成はなかなかに複雑(だがアイディアは単純)で個人的にお気に入りです(形式的な定義は下図(論文中¹の図5))．

関連研究と発展

多くの読者は「語混合言語なんて変な言語クラスになぜ興味を持ったんだろう？」と思われるかもしれません．
私がこの奇妙な言語クラスに出会ったのは2年前に府中で開催されたDLT'18のことでして、カナダの学生さんが発表していた "Counting Subwords and Regular Languages"⁷という論文の講演で語混合言語について「パラメタ語の個数が2つの場合は$L_A(w_1, w_2)$が正規言語かどうかは多項式時間で判定できる」という結果が紹介されていました．
今回私が示したパラメタ語の個数に制限の無い一般の場合での正規性・文脈自由性の決定可能性については、計算量はよくわかっておらず、私の証明から(おそらく)$\mathrm{EXPSPACE}$には所属すると思いますがより効率の良いアルゴリズムの存在については future work になるかもしれません．

実は理論的背景としては制約オートマトン(constrained automaton)と呼ばれるより広い言語クラスを認識するオートマトンの拡張モデルがあり、今回の結果は制約オートマトンの文脈自由性の特徴づけの前哨戦といった位置づけに私の中ではあります．
制約オートマトンは理論的に非常に美しいオートマトンの拡張モデルで、従来のオートマトン理論の良いところがかなり使えるながらも計算能力が非常に高い計算モデルです．
特に、制約オートマトンの中でも無曖昧という性質を持つモデル⁸で受理される言語クラス($\mathrm{UnCA}$)は非常に良い閉包性(和集合、積集合、補集合、反転、左右からの剰余すべてに閉じてる！)を持ち、さらにあらゆる問題が決定可能(無限性・正規性・普遍性(すべての語を含むか?)・等価性・包含性すべてが決定可能！！)という性質を持った豊かな言語クラスです．制約オートマトンは、オートマトン理論の抽象論であるモノイドの rational subset の美しいコンビネーションで定義でき...(制約オートマトンの解説を書き出すと止まらなくなるので、解説はまたの機会に譲ります．

無曖昧な制約オートマトンが入力されたときに、そのオートマトンの受理する言語が正規であるかどうかは決定可能であることが既存研究⁸で示されています．
語混合言語は常に無曖昧な制約オートマトンで受理することができるので、系として語混合言語の正規性の決定可能性もこの結果から出てきます．
私の今回の結果は、語混合言語という特殊な制約オートマトンで受理される言語について、正規性を次元という新しい概念によって特徴づけ、さらにその拡張として文脈自由性も特徴づけたという話の流れになります．最も興味のある今後の課題は無曖昧な制約オートマトンに対する文脈自由性で、こちらはある程度証明が進んでいます．

Ryoma Sin'ya: Context-Freeness of Word-MIX Languages, 論文の full version はこちら． ↩
ちなみに$\mathrm{MIX}$がインデックス言語(文脈自由言語の自然な拡張の1つ)であるかどうか？は有名な未解決問題です． ↩
拙著サーベイ論文「オートマトン理論再考」の3節で解説しています． ↩
「オートマトン理論再考」の定理2.3． ↩
「オートマトン理論再考」の未解決問題1． ↩
美しすぎん？？ ↩
Charles J. Colbourn, Ryan E. Dougherty, Thomas F. Lidbetter, Jeffrey Shallit: Counting Subwords and Regular Languages, https://arxiv.org/abs/1804.11175 ↩
Michaël Cadilhac, Alain Finkel, Pierre McKenzie: Unambiguous Constrained Automata, https://link.springer.com/chapter/10.1007/978-3-642-31653-1_22 ↩