26.1.3 正規表現とオートマトン

正規表現はテキスト検索のための手段である一方，理論的には有限状態オートマトンと深い関わりがあります．事実としては，正規表現は必ずオートマトンで記述でき，逆にオートマトンで受理される文字列は必ず正規表現で記述できます．この節では両者の対応関係について議論します．なお，以下の議論は主に Michael Sipser 著，渡辺治・太田和夫監訳『計算理論の基礎』(共立出版) に従い，記号は全てこの本に合わせてあります．

アルファベットと言語

私たちは普段ひらがな，カタカナ，漢字などの日本語の文字や英語圏のアルファベットなど，色々な文字を使っています．しかし以下の議論では，具体的に「どの文字を使っているか」という情報は大事ではありません．というのも，正規表現そのものの構造を見るだけなら文字の種類は関係ないからです．たとえば a+ という正規表現は a, aa, aaa, … という文字列にマッチし あ+ という正規表現は あ, ああ, あああ, … という文字列にマッチします．これらの正規表現でマッチする文字列は違いますが，しかし + だけを使っているという構造は全く同じです．
そこで有限集合 Σ を 1 個固定し，Σ の元をアルファベットと呼ぶことにします．例えば英語の場合，アルファベットの集合は Σ={a, b, … ,z} となります．以下の議論ではアルファベットに条件を全く課さないので，アルファベットの取り方に依存しない結果が導かれます．
また，アルファベットの有限列からなる集合を「言語」と呼ぶことにします．たとえばアルファベット Σ が Σ={a, b, … , z} のとき，集合 {a, b, c} , {apple, lemon, orange} や { a, aa, aaa, …} は言語です．このように「言語」を定義することにより，オートマトンや正規表現に関する議論を正確に定式化することができます．

オートマトン

それでは，オートマトンとは何であるかを説明します．1 年生の授業「情報」の教材としてexternalオートマトンシミュレータ が用意されているので，これを併用しながら説明します．

 決定性オートマトン

オートマトンが何かを全く知らない人は，上記のオートマトンシミュレータを使って簡単なオートマトンを作ってみてください．操作をしてみれば分かると思いますが，オートマトンは大雑把にいうと

  • いくつかの状態を持つ機械で
  • 何か入力があると，それに応じて別の状態へと移動する

というものです．またオートマトンは「終了状態」という特別な状態を持っています．
これを厳密に定式化すると次のようになります．オートマトンとは「アルファベット Σ」「状態と呼ばれる有限集合 Q」「開始状態と呼ばれる Q の元 q0」「終了状態と呼ばれる状態全体の集合 F⊂Q」「遷移函数と呼ばれる写像 δ:Q×Σ→Q」の 5 つ組 M=(Q,Σ,δ,q0,F) を指します．わざわざ遷移函数という言葉を出しましたが，要は「どの状態でどの入力が来たらどの状態に移動するか」というデータが δ です．
オートマトンの一番最初の状態は開始状態です．オートマトンに文字列を入力すると，オートマトンは文字列を 1 文字ずつ順番に読んでいき，遷移函数に応じて状態を移動させます．そこでオートマトン M=(Q,Σ,δ,q0,F) が文字列 w=w1w2…wn が受理されるということを，次の 3 条件を満たす状態の列 r0,r1,…,rn が存在することと定めます．

  1. r0=q0
  2. i=0,1,…,n-1 のとき ri+1=δ(qi,ri)
  3. rn ∈ F

オートマトン M に対し，M が受理する文字列全体の集合を M が認識する言語といい L(M) と書きます．また，あるオートマトンによって認識される言語を正規言語といいます．

非決定性オートマトン

以下で正規表現と正規言語の議論をするにあたっては，オートマトンの概念を拡張して非決定性オートマトンというものを導入するのが便利です．非決定性オートマトンはいわば「並列計算可能なオートマトン」で，一つの文字を入力したときに状態を分岐させることができます．これもオートマトンシミュレータで “Nondeterministic Finite Automaton” を選択すれば作ることができます．まずはシミュレータをいじって感覚をつかむと良いでしょう．
これを決定性オートマトンと同様に定式化すると次のようになります．一般に，集合 X に対して P(X) で X の巾集合 (つまり X の部分集合全体) を表します．オートマトンとは「アルファベット Σ」「状態と呼ばれる有限集合 Q」「開始状態と呼ばれる Q の元 q0」「終了状態と呼ばれる状態全体の集合 F⊂Q」「遷移函数と呼ばれる写像 δ:Q×(Σ∪{ε})→P(Q)」の 5 つ組 N=(Q,Σ,δ,q0,F) のことです．ただし ε は空の文字列を表します．また N が文字列 w=w1w2…wn が受理されるということを，次の 3 条件を満たす状態の列 r0,r1,…,rn が存在することと定めます．

  1. r0=q0
  2. i=0,1,…,n-1 のとき ri+1 ∈ δ(qi,ri)
  3. rn∈F

要は，遷移先の状態が複数あることを表現するために遷移函数の値がQ の部分集合になるようにしたわけです．N が文字列を受理することの定義や N の認識する言語 L(N) の定義は，決定性オートマトンのときと同じです．
非決定性オートマトンは決定性オートマトンの拡張ですが，非決定性オートマトンで認識可能な言語は決定性オートマトンでも認識可能です．実際，非決定性オートマトン N=(Q,Σ,δ,q0,F) に対して決定性オートマトン N=(M’,Σ,δ’,q0‘,F’) を

  • M’:=P(Q)
  • X∈Q’ (つまり X⊂Q) と a∈Σ に対し δ'(X,a):={ δ(x,a) | x∈X}
  • q0‘={q0}
  • F’={X∈Q’ | X∩F は空でない}

で定めれば L(M’)=L(N) となります．したがってある言語が正規言語であることを示すには，それを認識する非決定性オートマトンが作れれば良いということになります．

正規表現

前節 hwb26.1.2 正規表現の文法 で正規表現の書き方を一通り説明しましたが，ここで扱う正規表現は文字列の連結，繰り返しと選言のみを考えます．つまり文字列， * と | のみで書ける正規表現を考えるということです．一見するとこの制限によって正規表現の機能が弱くなる気がしますが，実際には全ての正規表現は文字列と * と | だけで書くことができます．ですのでこれだけ使えれば十分です．
より形式的にいうと，正規表現は次のように再帰的に定義されます．

  1. アルファベット Σ の元
  2. 空文字列 ϵ
  3. 空集合
  4. R1, R2 が正規表現のとき，和集合 R1∪R2
  5. R1, R2 が正規表現のとき，連結 R1R2
  6. R が正規表現のとき R*

オートマトンと正規表現の等価性

それでは，オートマトンと正規表現が同じ能力を持つことを証明しましょう．

正規表現で記述される言語が正規言語であること

いま考えている正規表現は連結，合併と *  という 3 つの操作のみで定義されます．そこで正規言語にこれらの操作を施したものが再び正規言語であることを示せば，正規表現で記述される言語が必ず正規言語であると言えます．
この証明は簡単です．まず連結操作について考えます．A1, A2 を共に正規言語とし，これらを認識する非決定性オートマトンをそれぞれ N1, N2 とします．このとき N1 の全ての終了状態から N2 の開始状態へ空文字列 ε で遷移できるようにすることで新しい非決定性オートマトン M を作ると，M は明らかに A1A2 を認識します．よって正規言語は連結操作で閉じています．また合併操作について考える時は，N1, N2 を単純に並べた後に新しい開始状態 q を付け加え，q から N1, N2 それぞれの開始状態へ空文字列 ε で遷移できるようにします．こうしてできる非決定性オートマトンは A1∩A2 を認識します．
最後に * 操作を考えます．正規言語 A を認識する非決定性オートマトン N を取ります．このとき N の全ての終了状態から開始状態へ空文字列 ε で遷移できるようにし，終了状態は元々の N の開始状態のみとすれば，新しくできた非決定性オートマトンは A* を認識します．かくして，正規表現で記述される言語は必ず正規言語であることが示されました．

正規言語が正規表現で記述できること

逆方向の証明をするには，非決定性オートマトンをさらに一般化し，状態遷移のラベルとして正規表現を使うことを許すようにします．いま，一般化された非決定性オートマトン N の中の 3 つの状態 q1, q2, q3 について

  • q1 から q2 へ直接遷移するラベルが R1
  • q1 から q3 へ直接遷移するラベルが R2
  • q3 から q2 へ直接遷移するラベルが R3
  • q3 から q3 へ直接遷移するラベルが R4

であったとします．このとき状態 q3 を取り除いて q1 から q2 へ遷移するラベルを R1∪(R2R3*R4) 書き換えて新しいオートマトンを作ると，状態数を 1 個減らして同じ言語を認識する一般化された非決定性オートマトンを作ることができます．この操作を繰り返して状態を 2 個まで減らせば，L(N) を認識する正規表現が得られます．こうして，オートマトンと正規表現の等価性の証明が完成しました．

正規言語でない言語

最後に正規言語でない言語について簡単に紹介します．世の中には「正規表現では決して書くことのできない」言語というものが存在します．その存在を示す鍵となる命題が，次のポンピング補題です．

ポンピング補題: A を正規言語とする．このとき，ポンピング長と呼ばれる正整数 p が存在し，A に属する長さ p 以上の文字列 w は必ず次の条件を満たす文字列 x, y, z の連結 w=abc に分解できる．

  1. 任意の非負整数 i に対して xyiz は A の元である．
  2. |y|>0
  3. |xy|≦p

証明は次の通りです．A を認識するオートマトンを M=(Q,Σ,δ,q0,F) を一つ取り，Q の元の個数 #Q を用いて p:=#Q+1 と定めます．そして A に属する文字列 w=w1w2…wn が |w|≧p を満たすとします．オートマトン M に w を入力したときの状態遷移の列 r0=q0, ri:=δ(ri-1,wi) とすると |w|≧p>#Q+1 だから，鳩の巣原理から r0, r1, … , rn の中に必ず同じものがあります．そのような重複する 2 個の文字のうち，最初に現れるものを rk, rl (0≦k<l≦n) とし x:=w1…wk, y=wk+1…wl, z=wl+1…wn とすれば，x, y, z は上の条件を全て満たします．これでポンピング補題が証明できました．
この補題を使うと，たとえば「回文全体の集合」が正規言語でないことが分かります．アルファベットを Σ={a, b} として A を Σ の文字からなる回文全体の集合とします．仮に A が正規言語だとすると，ポンピング長 p が存在します．そこで w=apbap とします．するとポンピング補題の条件を満たすよう， w を 3 つの部分文字列 x, y, z の連結 w=xyz と表すことができます．すると 1 番目の条件から xyyz は A の文字列です．一方 3 番目の条件 |xy|≦p から，x, y は共に a だけからなる文字列で，w の中に唯一存在する b は z に含まれています．すると a の個数を考えれば， xyyz が回文ではありえないと分かります．したがって矛盾が生じるので，回文全体の集合は正規言語ではありません．
この事実は直感的に説明すると次のようになります．回文であるかどうかを判定するには文字列の前半部分を記憶しなければいけませんが，一方でオートマトンは状態を有限個しか持たないので文字列の記憶能力を持ちません．よってオートマトンで任意の回文を判定することは不可能です．
もちろん，オートマトンよりも高度な機能を持つ機械を用意すれば正規言語より広いクラスの言語を記述することが可能です．そのような機械の例としては，たとえばプッシュダウン・オートマトンや Turing 機械があります．これらについて詳しく知りたい人は hwb26.5 参考文献 に挙げた参考文献に当たってください．