【シプサ】2 文脈自由言語 (その3)

文脈自由文法(CFG)とプッシュダウン・オートマトン(PDA)の等価性をなんとなく理解できた。理解できるまで4時間くらいかかった。たぶん頭のよい人は5分くらいでわかるんだろう。5分で理解できるようになるにはどうしたらいいんだろう。以下はメモを多少。

• まず、計算理論における「言語」の指すものがわかった。それは例えば日本語をここでいう「言語」というとき、「日本語として認められるすべての文字列の集合」という巨大な集合を考えておりその集合を言語と呼んでいるのだ。だからC言語を「言語」として考えるとき、それは「C言語で書かれていると認められる全ての文字列を含む集合」を考えている。Common Lispを「言語」として考えるとき、それは「Common Lispで書かれていると認められる全ての文字列からなる集合」のことである。こういう考え方をするとき、マクロがビルドインされているCLはとんでもないことになるのでないか、という不安と期待を感じる。現時点では正直不安の方が大きいのだが。。。
  
• 言語はそのようにいくら巨大とはいえ「文字列の集合」にすぎないのだが、それを調べるのに2つの方法論がある。ひとつは、ある文字列が与えられたとき、それがその集合に属するかどうかを判定できる判定機構をつくり、その機構のあり様をみてみるというやり方。もうひとつは、その言語に属する文字列を全て生成可能なような生成機構をつくり、その機構のあり様をみてみるというやり方。
  
• 正規言語と呼ばれる言語クラスを考えてみる。まず、その言語クラスに属する言語たちを特定するために、それは有限オートマトン(DFA)が存在するような言語であるとする。すると、正規表現という生成機構で表現可能な言語どもは正規言語であるし、逆も真であることがわかる。これが等価性。
  
• 正規言語: {判定機構:DFA, 生成機構:正規表現}ということになる。
  
• さて、次に、生成機構としてCFGを採用したときに表現可能な言語のすべてを総称して文脈自由言語と呼ぶことにする。正規言語のときとは定義の仕方が逆になっているが、まあそれはどうでもいいこと。
  
• で、文脈自由言語: {判定機構:PDA, 生成機構:CFG}ということを確認したい、ということ。
  
• 文脈自由言語(CFL)はCFGが生成するものとして定義されているので、これを確認するには、
  
• PDAが認識(判定)できるものはCFLである、ということと、CFLならばPDAで認識できる、ということを確認すればよい。
  
• いいかえると「PDAが認識できる言語に対して、CFGを構成できる」ということと、「CFGが存在する言語に対して、PDAを構成できる」ということ。
  
• 後者の方が簡単なので、本書では後者から確認している。
  
• 「CFGが存在する言語に対して、PDAを構成できる」
  
  
  
  • ポイントは非決定性。
    
  • CFGの変数および終端文字はスタック・アルファベットとする。
    
  • はじめのセットアップとして、スタックに開始変数をいれておく。
    
  • これが種となって、PDAは、CFGに従って、入力をまたず、非決定にがんがん勝手に分岐していく。生成規則に従って変数を左辺の表現にどんどん替えていくのだ。これがCFGにて認識可能なすべての文字列をつくってしまう。(非決定性の力はすさまじい。。。)
    
  • するとそれらの分岐はそれぞれにスタックを持ち、その中には認識可能な文字列が入っている、というイメージ。
    
  • 実際にはちょっと違っていて、S->aTbとかの分岐においては、aがスタックの先頭にいるので、Tの分岐ができない。
    
  • なので、その分岐は入力を待つ形になる。で、入力として、aがくればa->εしちゃって、Tが先頭になり、また分岐地獄が始まる。
    bがくればその枝は破棄する。
    
  • で、スタックが空になったタイミングではいつでも自動的に受理状態に遷移する。すると、そこで入力文字列が終わっていれば受理されるし、まだあれば、その枝は破棄される。
    
  
  
• 「PDAが認識できる言語に対して、CFGを構成できる」
  
  
  
  • これのポイントは「PDAに含まれる2つの状態の組の全てに対して、その組ごとに、それらの間の一方から一方に遷移するような文字列を生成するCFGを構成できる」ということ。
    
  • おまけ条件があって、「遷移にあたってどちらの状態もスタックは空である」を満しているものとする。
    
  • ポイントはそれとして、まずPDAを別のPDAに等価変形する。
    
    
    
    • ただ一つの受理状態をもつようにする。
      
    • 受理する前にスタックを空にする。(受理状態はスタックが空である)
      
    • 全ての遷移は、ポップかプッシュのどちらかであるようにする。これには状態を足したり遷移を足したりすることが必要になることもある。
      
    
    
  • このPDAをPと呼ぶ。P = {Q,Σ,Γ,δ,q_0,{q_accept}}とする。これに対して、CFGたるGを次のように構成する。
    
    
    
    • p,q∈Qについて、ApqをGの変数とする。
      
    • 開始変数はAq_0q_acceptとする。
      
    • ΣをGの終端記号とする。
      
    • 規則の構成。
      
      
      
      • App -> ε。
        
      • Apq -> AprArq
        
      • p,q,r,s∈Q; t∈Γ; a,b∈Σεに対して、「δ(p,a,ε)が(r,t)を含み、δ(s,b,t)が(q,ε)を含む」ということがあるなら、Apq -> aArsb
        
      
      
    
    
  • さて、これによってPDAからCFGを構成する「とある方法」を明確にした。
    
  • で、どうしたいかというと、この「とある方法」にて構成したCFGにおいて、
    
  • 「Apqが生成する文字列は全て、スタック空の状態pからスタック空の状態qに遷移するようにPDAが計算する」
    
  • と、その逆たる
    
  • 「スタック空の状態pからスタック空の状態qに遷移するようにPDAが計算する文字列の全てを、Apqが生成できる」
    
  • ということが実は成立している、ということ。
    
  • これが成立していること自体は、帰納法を使えばかんたんにわかる。
    
  • で、これが成立しているということがどういうことかというと、
    
  • ここで確認したことをAq_0q_acceptにに適用すれば、
    
  • 「Aq_0q_acceptが生成する文字列たちと、スタック空の状態q_0からスタック空の状態q_acceptに遷移するようにPDAが計算する文字列たちとは等価である」
    
  • が言えたということ。これは確認したかったこと、そのもの。
    
  
  

という感じかなぁ。こつこつ。