文脈自由言語とプッシュダウンオートマトン

今日から第二部。第一部でやったことの一般化になっているらしい。どう一般化になっているかはまだ分からないけど。

• 生成規則(るーる)を使って考える
  • この方法を使うと正則表現のようなことができそう?
  • 規則はrecursiveに(ちょっと違うか)定義されることもある(A => aAとか)

• 回文は正則表現だと表現できなかったが、生成規則だと回文が表現できる!!
  • AB => BAとかはダメっぽい
    • 文脈自由文法(CFG)よりさらに大きいクラスに属するらしい => CSG
    • CSG(Context Sensitive Grammer)、PSG(Phrase Structured Grammer)などがあるらしい

• Context-freeの意味
  • 「文脈が自由」ではなく、「文脈から自由」という意味

• は正則言語ではないが、CFLになっている!

• CFGは自然言語の単純なモデルと考えることができる
• これでコンパイラのあれとかgenerateはできるけど、parsingしてvalidなものかを確認するのってえらく難しそう...
  • あとでやるのかな

• 正則言語は語彙解析、CFGは構文解析に使われる

• CFLは正則言語を真に含んでいる(!)
  • CFGのパターンをある程度制約してやったものが正則言語のクラスと一致することを示す
    • これはCFGの特殊ケースとなっている
  • 結構strictに制約する