できれば、いくつかの文脈自由文法を用いて説明してください。
http://ja.wikipedia.org/wiki/%E3%83%81%E3%83%A7%E3%83%A0%E3%82%B9%E3%82%AD%E3%83%BC%E6%A8%99%E6%BA%96%E5%BD%A2
まず定義の確認です。
文脈自由文法とは、形式文法の置き換え規則が全て
という形で表されるものです。
ただし、ここでは1つの非終端記号であり、は非終端記号と終端記号からなる長さ0以上の系列(文字列)です。
つまり、1つの非終端記号を別の何かに置き換える規則しかないものならばそれは文脈自由文法と呼びます。
一方チョムスキー標準形の定義は、形式文法の置き換え規則が
の形からなるもののことです。
ただしは非終端記号では終端記号、は開始記号、は空系列です。
言い換えれば、形式文法の置き換え規則が
・1つの非終端記号を2つの非終端記号で置き換えるもの
・1つの非終端記号を1つの終端記号で置き換えるもの
・1つの開始記号を空系列に置き換えるもの
しかない場合、この形式文法をチョムスキーの標準形と呼びます。
つまりチョムスキー標準形の置き換え規則は全て1つの非終端記号を置き換えるものなので、文脈自由文法です。
(開始記号も非終端記号です)
よってご質問の前半である
「チョムスキー標準形で表される文法は全て文脈自由」
が言えるわけです。
さて、ご質問の後半部分である
「文脈自由文法はこれと等価なチョムスキー標準形の文法に書き換えることができる」
ことを示すにはやや長すぎるのでブログのほうに書きました。ご了承下さい。
以下、一般の文脈自由文法からチョムスキー標準系への変換の一例を書いておきます。
言語を生成する文脈自由文法
をチョムスキーの標準形に変換する。
ただし、置き換え規則は
(1) 新しい開始記号の導入
新しい開始記号を導入して文法を次のように変換する。
ここで、置き換え規則は
(2) ε規則の除去
開始記号以外からのε規則があるので、これを除去し文法を次のように変換する。
ここで、置き換え規則は
(3) 書き換え規則の除去
書き換え規則はないので除去の必要はない
(4) 長文規則の除去
長文規則があるので、これを除去し文法を次のように変換する。
ここで、置き換え規則は
(5) 最終処理
終端処理を含む2文字への置き換えの代わりに
を導入し、終端処理2文字への置き換えの代わりに
を導入する。
以上によりチョムスキー標準形の形式文法
ここで、置き換え規則は
を得る。