形式言語 チョムスキー標準形

１．文脈自由文法G=({S},Σ,P,S) が L(G)={0 ^n 10^n ∣n≥0} を生成するとき、生成規則の集合 P を書け。ただし、{S} は G の非終端記号（non-terminal symbol）の集合（set）である。

２．G をチョムスキー標準形にした文法の生成規則の集合を書け。

この問題を解いています。自分の解答に自信がないので間違っていたら教えて欲しいです。

１． P={S→1,S→0S0}
２．P_CNF={S→X_0 Y_1,　S→1,　Y_1→SX_0,　X_0→0}

No.1 回答者： stomachman 回答日時： 2025/05/11 14:17

間違っているかどうかがモンダイなのではなくて、答だけ示して自信がないとか言ってることがモンダイなんですよ。

それは1.と2.が同値であることの証明をやっていないからでしょう。だったら、たとえ間違っていなくたって、ただのマグレ当たりってことじゃないか。