※本エントリは人力検索はてなの質問http://q.hatena.ne.jp/1233731707に対する回答の一部です まずいくつかの用語を定義することにします。 のような置き換え規則をε規則と呼ぶ(は非終端記号、は空系列) のような置き換え規則を読み換え規則と呼ぶ(は非終端記号) (uは長さが3以上の系列)のような規則を長文規則と呼ぶ 上に挙げた3つの置き換え規則は、文脈自由文法の置き換え規則としては許されるものですが、チョムスキー標準形には当てはまらないものです。 (ε規則は左辺の非終端記号が開始記号の場合だけはチョムスキーの標準形に当てはまります) 文脈自由文法の置き換え規則の中で上に挙げたものがある場合、その置き換え規則を除去して等価な置き換え規則を追加していけばチョムスキー標準形になるという理屈です。 (1) 新しい開始記号の導入 まず、文脈自由文法の開始記号を別の開始記号に置
