Chomsky標準形

計算機科学

Information

ver date memo
1.0 2013/05/25 first

文脈自由文法

次の４つ組を文脈自由文法という。
G = (V, \Sigma, R, S)
ここで、

  1. Vは変数(variable)と呼ばれる有限集合
  2. \Sigmaは終端集合(terminal)と呼ばれる、Vと共通部分を持たない集合
    つまり\Sigma\cap V = \empty
  3. Rは変数及び変数と終端記号から成る文字列で構成される規則(rule)の有限集合
    例) A\to w where A\in{V}, w\in{V\cup \Sigma}
  4. Sは開始変数 S\in V

Chomsky標準形

次の生成規則のみからなる

  1. A\to BC
  2. A\to \alpha
  3. S\to \epsilon

where A,B,C\not\in\Sigma , \alpha\in\Sigma, \epsilonは空列
尚、3つ目の定義は、定義に含めない場合もある。

性質
  1. Chomsky標準形で表すことのできる文法はすべて文脈自由である。
  2. すべての文脈自由文法は、等価なChomsky標準形の文法に書き換えられる。

Chomsky標準形を何に使うのか？

要点は、Chomsky標準形に書き換えることによって文法が単純化されると言う事。
文脈自由文法で、ごちゃごちゃと定義された文法を上記の3式のいずれかのパターンで書き換えられるので使いやすく成るでしょ？
という事みたい。
(CYK法で使うようである)

メモ

非終端記号

非終端記号 = 構文変数
置換されうる記号

終端記号
　其れ以上変換されない

文法
1. x can become xa
2. x can become ax

xは非終端記号
aは終端記号（其れ以上変換されない記号）