complexity-theory - 提供一个生成奇数长度语言的上下文无关文法 {w = 0*1* : |w| 很奇怪}

Question

提供一个上下文无关的语法，生成以下语言

Σ = {0,1}: {w = 0*1* : |w| 很奇怪}

我的解决方案：

S->AB|0|1

A->0A|^

B->1B|^

但是使用这种语法，我们可以创建偶数个字符串。

我想要产生 L = {0,1,000,111,001,011,00000,11111,00001,00011....}

Answer 1

An odd number is the sum of an odd number and an even number, so sentences in the language are either an odd number of 0s followed by an even number of 1s, or an even number of 0s followed by an odd number of ones. Moreover, an odd number is an even number plus one; if we make that substitution in the preceding description we get "an even number of 0s followed by either 0 or 1, followed by an even number of 1s". Since every even number is either 0 or two more than an even number, we end up with.

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

or

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