チョムスキー正規形の導出に2n-1ステップが必要であることを証明するにはどうすればよいですか？

Question

私は次のことを証明しようとしている：

Gはチョムスキー標準形で文脈自由文法であれば、長さN ≥ 1のL（G）を所属wが、その後、任意の文字列のために、それは正確に2n個必要ですwを導出するための-1ステップ。

どうすればこのことを証明できますか？ヒントとして

Answer 1

- チョムスキー標準形ですべての生産は、いずれかの端末Xの非終端AおよびBのフォーム

S → AB、またはフォーム

S → Xを有しているので、

その後、次のように動作するストリングを導き出す：

• 正確にn個の非終端記号の文字列を作成し、次に
• 各端末を単一の端末に展開します。あなたが+1非終端記号の正味利得のための2つの非終端（+2）と、ワン非終端（-1）を置き換えるため第一形態の

適用プロダクションは、1 + kにkから非終端記号の数を増加させるであろう。 1つの非終端記号で始めるので、これは最初の形式のn - 1個のプロダクションを行う必要があることを意味します。次に、非終端記号を端末に変換するために、n +（n-1）= 2n-1個のプロダクションを与えるために、2番目の形式のn個以上のものを必要とします。

正確にはがこの数多く必要であることを示すために、私は矛盾で証拠を提示し、それ以上のものでもそれ以下のものでもできないことを示してください。ヒントとして、作成された各タイプの作品の数を数え、それが2n-1でなければ文字列が短すぎるか、まだ非終端記号が残っていることを示してください。

希望すると便利です。