私は、次の言語のための文脈自由文法をデザインしたい：文脈自由文法
L = {電子ワット{（、）} * | |>（S）S -
S：Wは、私は、次の文法を提案
}バランスでありますE
講義で提案された解決策があるのに対し：
S - >（S）| SS | E
私の解決策には何か問題があるかもしれません。 Iのような様々なケースのための文法の両方走っ：
（（）（））、（）（）（）、及び（（））（）
を、両方のCFGを受け付けこれらの文字列。
誰かが私のCFGでカバーしないケースは何か助けてもらえますか？それとも両方とも同等ですか？または、最終状態に達するのに必要な遷移の数が異なります。
どちらの文法も同じ言語を生成するため、どちらも正しくありません。
私はあなたが好む理由は明確ですが、これは要件の一部ではないためです。多くの人が他の答えを理解しやすいと思っているようですが、それは要件の一部でもなく、それは非常に主観的な基準です。
riciが正しいです。文法が同等であることを示すために（同じ言語を生成する）、他の文法を複製して同じ文字列を生成することができます。次のように
例えば、提案された文法はEを(S)S生成し、することができます
`S => SS => (S)S` and `S => E`.
次のように他の文法を複製することができますあなたの文法：
S => SSについては
`S => (S)S => (S)`
`S => E`
、あなたが実際にすることはできませんそれを複製するか、または講義の文法ができる他の任意のS^nである。ターミナルの文字列がカバーされている限り、これらのすべてをカバーする必要はないので、これは問題ありません。
`S => (S)S => (S)(S)S => ... => (S)^n S => (S)^n`
今、あなたが行われています。この1のために、S^nは最終的にそのSが(S)（他のルール）に変更し、左側から作業の全てが必要であることに注意してください。
また、（a）文法で生成されたすべての文字列がLであることを証明することもできます。 （b）文字列がLの場合、文法によって生成されます。これは、括弧のペア数などの誘導によって行うことができます。
ベースケース：n = 0の場合、文字列はEであり、これはLです。 n = 0の唯一の文字列はEで、私たちの文法によって生成されます。
誘導仮説：Lであると、私たちの文法によって生成された括弧のkペアを含めて最大で、すべての文字列、およびまで、私たちの文法によって生成された括弧のkペアを含むとL内のすべての文字列。
誘導のステップ：私たちは、文法によって生成された括弧のk+1ペアを持つすべての文字列がLであり、括弧のk+1ペアとL内のすべての文字列は、私たちの文法によって生成されていることを示しています。括弧のk+1ペアがルールS => (S)Sを使用して、当社の文法によって生成されたと
と仮定文字列w。次いで、X is balanced, thusis therefore balanced sinceワットw =（x）はyのwhere X and Y are words in L with fewer than K + 1 pairs of parentheses. But then they are balanced by the induction hypothesis.（X）is balanced and（X）Y = w`もあります。
k+1の括弧を含む文字列wがLであるとします。次に、Lの定義によって、wがバランスされます。括弧のバランスのとれた文字列は、左と右の括弧の数が同じでなければならず、任意の接頭辞で右かっこと同じ数の左かっこを持つ必要があります（したがって、接尾辞には左かっこと同じ数の右かっこが必要です）。最初の左括弧と最初の右括弧を選択し、接頭辞には左右の括弧が同数含まれるようにします。これは部分文字列(x)のwです。その部分文字列の後には、右括弧と同じ数の左括弧が必要であり、任意の接頭辞の右括弧が少なくとも同数必要です（これはwのバランスが取れた条件を満たすためです）。したがって、後で何が来るのか - それをyと呼ぶことにする - また、括弧の平衡した文字列でなければなりません。 （適切な）部分文字列としては、xとyの両方がw（括弧の数が少ないペア）より小さくなければならず、両者はバランスが取られている必要があり、両方ともLである必要があります。しかし、両方とも文法によって生成され、文法はS => (S)Sという生産物を含んでいるため、(x)yを生成します。
QED
あなたの答えのためのわかりましたありがとう。 – yogeshagr