奇数長の言語を生成する文脈自由文法を提供する（w = 0 * 1 *：| w |奇数}

Question

を超える文脈自由文法を提供する

Σ= {0,1}：{w = 0 * 1 *：| w | 0 | | 1

A-> 0A |^

B-> 1B |^

しかし、この文法を使用して

S-> AB：

}奇数私の解決策であります私たちは偶数の文字列を作成することができます。

Iは文章中のSO L = {0,1,000,111,001,011,00000,11111,00001,00011 ....}

Answer 1

を生成文法が奇数、奇数と偶数の和である必要言語は、0の奇数、1の偶数、または0の奇数のいずれかに続く奇数である。さらに、奇数は偶数+ 1です。前の説明でその置換を行うと、「0の偶数、0または1の後に1の偶数が続きます」という結果が得られます。すべての偶数は0または2以上の偶数であるため、最終的に終了します。

S -> A 0 B | A 1 B 
A -> ε | A 0 0 
B -> ε | B 1 1 

または

S -> 0 | 1 | 0 0 S | S 1 1