形式言語理論における「言語」を、「バリデーション」と関連づけて整理

昔に大学の講義で「形式言語理論」を学んだ際、数学的な表現が多くて何を言っているのかわからなかった。当時はプログラミング等で正規表現を使ったことも無かったため、身近な経験と結びつけられなかったせいもあると思う。

今ならプログラミングの経験を生かして整理できるかもしれないと思い、再勉強してみることにした。特に**「言語」**のあたりがあやふやだったので、正規表現の理解に役立つ程度にまとめる。

• 触れること
  • 文字、文字列、言語、言語のクラス
  • 言語の演算
  • 正則言語と正則表現
• 触れないこと ※講義資料で難しいのはこちらなのだが…
  • 有限オートマトン
  • 反復補題
  • 形式文法
  • …

ポイント

• 「言語」はバリデーションを想像すればいい：許可する文字列を過不足なく集めたもの
• 「○○言語」と言ったとき、言語のクラス（≒汎用的なバリデーション手法の複雑さ）を表す場合と、単にある言語に名前を付けただけの場合がある

本記事での表記ルール

C言語やRubyのものを流用している。「言語の演算」の節では実際に試せるようRubyのコードを載せている。

• 「文字」はシングルクォートで囲む： 'a'
• 「文字列」はダブルクォートで囲む： "a"
• 「正則表現」（正規表現）はスラッシュで囲む： /a/
  • 演算子は形式言語理論のものでなくプログラミングに寄せる（ '+' → '|' ）
  • 完全一致として扱う（Rubyに忠実な書き方をすると /\Aa\z/ ）
• 変数・定数などはそのまま： a
  • ラテン文字、ギリシア文字、数学記号あたりを使う
  • 文字列や正則表現の中で展開したい場合は、式展開で表す： "#{a}", /#{a}/
• 集合は角括弧で囲む： ["a", "aa", "aaa", …]
  • 要素は全て同じ種類のもの（文字列なら文字列のみ）
  • 同じ要素は省き、順序は気にしない
  • 外延的記法で表し（実際に列挙し）、書ききれない部分は … で省略する

また、 "regular" をどう訳すかについては以下の形をとる。

• 基本的に理論側に寄せて「正則」とする：正則言語、正則表現など
• 例外的にプログラミング用語では「正規」とする：正規表現のみが該当

基礎概念

文字（letter）、記号（character, symbol）

事前に決めた何かしらの図形、と言うほか無い。 'A' でも 'あ' でも '🍎' でも文字になれるし、なんなら自前の画像でもいい、はず。

形式言語理論で言う「文字」は、あくまで互いに区別できるものであればよく、見た目には2文字以上あっても構わない（面倒なのでまず使わないが）。
プログラミングでも似たような状況はあり、例えばコードの文字列中の '\n' が改行コードという1文字を表すことはよくある¹。実際の正規表現でもバックスラッシュの有無は重要になる（メタ文字の節で触れる）。

アルファベット（alphabet）

利用すると決めた文字の集合。テキストファイルなどを扱う際に出てくるcharacter setと似た考え方（だが、そもそも「文字」の考え方に違いがある）。

基本的に文字の種類は有限とする。理論を考える際は2種類の文字さえあればいいことが多く、バイナリアルファベット Σ = ['0', '1'] がよく使われる。

文字列、記号列（string）、語（word）

文字を0個以上並べた列（sequence）。集合と異なり、同じ文字を何度も使えるし順序が考慮される。プログラミング的に言えば文字の配列。文字同士を区切る目印は無いが、アルファベットに従えば分解できる。

文字列の字数はよく「長さ」と言う。文字列型のあるプログラミング言語なら length の類で取得できることが多い。

• 長さは有限とする（＝終わりがある）が、いくらでも長いものを作れる。
• 長さ0の文字列 "" は空文字列と言う。この記事ではダブルクォートで囲うことで可視化するが、普通は見えないので ε または λ という定数で表すことが多い。
• 長さ1の文字列と単なる文字は異なる。ただしプログラミング言語によっては文字型がユーザーに提供されなく文字列で代用するものもある。

事前に「使う文字」を定義してある点が地味に重要で、文字を並べて作れないものはそもそも考えない。例えばアルファベットを Σ = ['00', '01', …, '7F'] （ASCIIの十六進表記）としてあれば、 "80" や "123" という文字列は存在し得ない。後で出すが、作れる全ての文字列の集合は Σ^∗ と表し、その枠の中で話が完結する。

言語（language）

目的に沿って選んだ文字列の集合。プログラミングと関連付けるなら、**「バリデーションで通す全ての文字列の一覧」**と考えればいい。

文字列はいくらでも長くできるので、それらの集まりである言語は無限集合となる場合がほとんど。ただし文字列は事前に決めたアルファベット内で作れるものに限る： L ⊆ Σ^∗ 。

場合によっては「○○言語」と名前を付けたりする。（これと次節の「言語」を混同しないこと）

• 例1: 素数言語 → 「文字数が素数個の文字列」の集合。
  • 仮にアルファベットを Σ = ['🍎'] とする。（文字数しか考えないので1文字でもいい）
  • この場合の素数言語は L = ["🍎🍎", "🍎🍎🍎", "🍎🍎🍎🍎🍎", …] 。
• 例2: 空言語 → 集合が空っぽ。つまりバリデーションは一切の文字列を通さない。
  • 具体的に書けば L = [] 。
  • 数学において空集合は ∅ で表すので、空言語も ∅ と書かれたりする。

○○言語

言語のクラスの分類。次のような言い方で出てくる。

• 「正則言語 L について、～が成り立つ。」
• 「したがって言語 L' は正則である。」

（前節の「言語」と紛らわしくなるのは、プログラミングの話でクラス名を出したとき、クラス全体か特定のインスタンスかわかりにくい場合と似ている。）

「チョムスキー階層」では4つに分類されていて²、階層とつく通り（その分類では）包含関係にある。もう少し階層を追加したものを、単純なものから順に、それぞれに属する言語の例と共に示す。

クラス	言語の例	備考
-	* MySQLの予約語 * UUID * 空言語	有限集合の例として階層を追加した
正則 regular	* MySQLの予約語でないもの * URL * HTML5が勧める妥当なメールアドレス	理論通りの正規表現でバリデーションできる限界
文脈自由 context-free	* RFC 5322が定める正当なメールアドレス * JSON * 文法的に正しい数式 * 回文
文脈依存 context-sensitive	* ユーザー名とパスワードが同じ文字列3 * XML * 素数言語
帰納的 recursive	?	必ず判定終了するアルゴリズムを作れる限界 チョムスキー階層には無いクラス
帰納的加算 recursively enumerable	* PCPが解を持つ文字列配列 * 終了するプログラム（と入力の組合せ）4	バリデーションを通る入力に対しては判定終了する
-	* 終了しないプログラム（と入力の組合せ）5	バリデーション不可能なものがあることを示している

それぞれの例は「より単純なクラスには属さないもの」として挙げたもので、クラス分類をもっと細かくすればより適切な位置に移動する可能性がある。身近にある言語はほとんどが文脈自由かせいぜい**+α**止まりなので、文脈依存をフル活用した例や帰納的な例はよくわからない。ただし帰納的加算に収まらないものがあることは理論上重要。

言語をバリデーションに関連づけている通り、「入力した文字列はこの言語に含まれるか」というYes/No判定をする問題を考えられる。その言語が属するクラスが単純であれば、作れるバリデーションは限定的なものの高速に判定でき⁶、複雑であれば判定に途方もない時間が掛かったりそもそも終了が保証されなかったりする。
→ https://ja.wikipedia.org/wiki/複雑性クラス

その他

文法（grammar）や計算モデルなどあるが、正規表現の入り口にたどり着くだけなら踏み込まなくていい。

言語の演算

言語は文字列の集合なので、事前にルールを作っておけば、複数の言語を元に新しい言語を生み出すこともできる。

※本当は事前に文字列の演算を定義しておく必要があるが、連結（連接）だけわかればいいので省略。

和集合（union）

2つの言語の少なくとも一方に含まれる文字列全て。バリデーションで言うとOR条件。

例えば L₁ = ["a", "b", "c"], L₂ = ["a", "aa", "aaa"] のとき、 L₁ ∪ L₂ = ["a", "b", "c", "aa", "aaa"] 。

和集合(Ruby)

lang1 = ["a", "b", "c"]
lang2 = ["a", "aa", "aaa"]

# 方法は色々
lang1.union(lang2)
lang1 | lang2
(lang1 + lang2).uniq

積（product）、連接（concatenation）

2つの言語から文字列を1つずつ選び連結して作れる文字列全て。（直積集合 × そのものや共通集合 ∩ とは異なる）

例えば L₁ = ["a", "b"], L₂ = ["x", "y", "z"] のとき、

• L₁ ⋅ L₂ = ["ax", "ay", "az", "bx", "by", "bz"]
• L₂ ⋅ L₁ = ["xa", "xb", "ya", "yb", "za", "zb"]
  • 連結するので、順序を逆にしたら結果は異なることが普通。
• L₁ ⋅ L₁ = ["aa", "ab", "ba", "bb"]
  • 同じ文字列同士だけ連結した ["aa", "bb"] ではないことに注意。

演算子 ⋅ は省略してもいい。

積(Ruby)

lang1 = ["a", "b"]
lang2 = ["x", "y", "z"]

# 直積集合を作ってからそれぞれ連結
lang1.product(lang2).map(&:join).uniq

累乗

指定回数だけ同じ言語の積をとる。 Lⁿ = L ⋅ L ⋅ ⋯ ⋅ L

再帰で表せば Lⁿ = L^n-1 ⋅ L となる。この場合は基本ケースとして L⁰ = [""] を定められる（単位元）。

※ L^R と書いてある場合は、累乗でなく各文字列の「反転」（reversal）を表している可能性が高い。 L^∗ や L⁺ は次節を参照。

累乗(Ruby)

lang = ["", "a", "b", "ab"]
n = 3

# Array#product にn個の引数を渡す
[""].product(*Array.new(n, lang)).map(&:join).uniq

閉包（closure）

言語 L のクリーネ閉包は L^∗ と表す。累乗で数を書いていたところがアスタリスクに置き換わっている。

クリーネ閉包は全ての累乗の和集合と定義される： L^∗ = L⁰ ∪ L¹ ∪ L² ∪ ⋯ 。もっと雑に言えば**「任意回の繰り返し」**。

• そのため、ほぼ全ての言語はこれを作用させると無限集合になる。バリデーションの幅が大きく広がる。
• L^∗ は必ず "" を含む。なぜなら和集合の項に L⁰ が入っているから。
  • 空言語 ∅ = [] のクリーネ閉包は、空文字列のみの言語になる。 ∅^∗ = [""]
  • L⁰ を省いた閉包を考えたいときは L⁺ という表記をよく使う。（これはクリーネ閉包と呼ばない）

言語でなくアルファベットに対してもよく適用される： Σ^∗ 。この場合は「アルファベット Σ 上で作成できる全ての文字列」という言語を表す。空言語の真逆で、バリデーションとしてはあらゆる文字列を通すことを意味する。

その他

主なものには以下がある。もちろんこれら以外にも適宜作っていい。

• 集合の演算
  • 共通集合 L₁ ∩ L₂
  • 差集合 L₁ - L₂ または L₁ ∖ L₂
  • 補集合 L̅ = Σ^∗ - L
    • 要するに「バリデーションで弾くもの全て」という真逆のバリデーションを作る操作。
• 文字列毎の演算
  • 反転 L^R
  • シャッフル L₁ ∨ L₂
  • 準同型写像 h(L)
    • アルファベット自体を変更してもいい
    • 非常に簡単な例は、trコマンドによる文字置換

「あるクラスの言語に対しある演算を施した結果は常に同じクラスに収まるか」というのは理論の興味の対象。例えば、

• 正則言語同士の共通集合は、必ず正則言語になる
  • 正規表現の「先読み」機能を使っても、正則言語の範囲内のバリデーションだけできる
  • 「先読み」を使わずに同じバリデーションを書く方法が何かしらある
• 文脈自由言語同士の共通集合は、文脈自由言語にならない場合がある
  • 〈前提〉正規表現の「再帰」機能を使うと、文脈自由言語のバリデーションができる
  • → 「再帰」と「先読み」を組み合わせた場合、文脈自由言語の限界を超えたバリデーションができる

https://en.wikipedia.org/wiki/Operations_on_languages に一覧がある。

正則言語と正則表現

正則言語に属する任意の言語はいくつかの基本ケースと3種類の演算によって組み立てられる、と定義される。この操作を式で表すようにしたのが正則表現（regular expression）。※正則文法とは異なる

正則言語の再帰的定義と、それぞれについての集合および正則表現での表記を、以下の表に示す。 L, L₁, L₂ は正則言語、 expr, expr1, expr2 はそれらに対応する正則表現。

正則言語なもの	集合での表記	正則表現での表記
空言語	∅ = []	理論: /0̸/, 実装: /(?!)/7
（空文字列のみ）	∅∗ = [""]	/(?!)*/ または //
ある1文字のみ	["a"], ["b"], …	/a/, /b/, …
和集合	L1 ∪ L2	/#{expr1}|#{expr2}/
積	L1 ⋅ L2	/(#{expr1})(#{expr2})/
クリーネ閉包	L∗	/(#{expr})*/

※「空文字列のみ」はクリーネ閉包で表せるため定義に入れなくていい。

演算には優先順位が決めてあり、必要に応じて丸括弧で順序を明示する。算数の数式（加算・乗算・累乗）と同じ。

• /ab*/ は /a(b*)/ と同じで、 ["a", "ab", "abb", "abbb", …] を表す。
• /(ab)*/ は ["", "ab", "abab", "ababab", …] を表す。

積の正則表現で演算子を不要と決めると、「ある文字列のみの言語」はその文字列のまま式になる。実用的。

• ["abc"] = ["a"] ⋅ ["b"] ⋅ ["c"] ⇔ /(a)(b)(c)/ = /abc/

メタ文字

任意の正則表現を作るには、見ての通り5つの「文字」 '(', ')', '|', '*', '0̸' が追加で必要になる。これらは正則表現で特別な意味を持つ文字（いわゆるメタ文字）であり、正則言語のアルファベットに含まれていてはいけない。

理論ではメタ文字を含まないように言語のアルファベットを定義すれば済む。一方で、現実の入力文字列には全ての文字が登場しうるので、正規表現専用の文字なんてものは用意できない。そこで、本来は1文字で表せていたものを2文字以上にして区別可能にする。基本的にはバックスラッシュを前に置くことがほとんどで、正規表現の実装により異なるが以下のように対応付けている。

文字	理論	基本正規表現 (BRE)	拡張正規表現 (ERE)
普通 'a'	'a'	'a'	'a'
普通 'b'	'b'	'b'	'b'
普通 '('	-	'('	'\('
普通 ')'	-	')'	'\)'
普通 '|'	-	'|'	'\|'
普通 '*'	-	'\*'	'\*'
普通 '\'	-	'\\'	'\\'
メタ '('	'('	'\('	'('
メタ ')'	')'	'\)'	')'
メタ '|'	'|'	'\|'8	'|'
メタ '*'	'*'	'*'	'*'

※ '0̸' = '(?!)' は色々と事情が異なるので載せていない

普通の文字とメタ文字とで被っていそうに見えるが、バックスラッシュが余らないように正規表現をパースすれば異なる「文字」として正しく分解できる。この方法を使えばメタ文字はもっと増やせるので、実際の正規表現では '.' や '\d' など様々なものに特別な意味を割り当てている。（その分、普通の文字と認識させる場合にバックスラッシュを置く必要も増えている）

参考

• 講義資料「形式言語理論」（宮野悟）
• 正規表現技術入門 最新エンジン実装と理論的背景

1. プログラミング言語で試す場合、シングルクォートではエスケープが働かないものもあるので注意。またOSによってはテキスト出力すると2文字（CR+LF）に変換されることもある。 ↩

2. 「生成文法」というものにどれだけ制約をつけられるかという分類。 ↩

3. 例えばURIで "#{user}:#{password}@#{host}:#{port}" とすると認証情報を入れられる（RFC 3986 section 3.2.1）。もちろん暗号化せずネットワーク上に流したりしてはいけない。 ↩

4. エミュレーターで実際にプログラムを実行すればいい。終了しない際はNoの判定を出さなくてもいい。 ↩

5. これは上の例の補問題。同じことを逆に言っているだけなのだが、Yesの判定を約束できないため帰納的加算ではない。 ↩

6. 正則言語なら入力文字列の長さに比例した時間で必ず判定終了できる。文脈自由言語なら文字列長の3乗に比例する場合がある。 ↩

7. 「否定先読み」という機能を応用したよくある表し方。理論では重要なので専用の文字（空集合や斜線付きゼロなど）を当てているが、実装では滅多に専用の表記が用意されていない。 ↩

8. BREの仕様には選択演算子は無く、実装によっては使えるというだけ。 ↩