A = { w | 的CFG w 具有奇数长度，其中第一个、中间和最后一个符号相等 }，w 来自 {0,1}*（epsilon 在语言中）

Question

A = { w | w 具有奇数长度，其中第一个、中间和最后一个符号相等 }，w 来自 {0,1}*（epsilon 在语言中）

ε, 011101010, 10101, 1 在语言中。

设 'e' 是 epsilon。

S -> 0X0X0 | 1X1X1 | e

糟糕，我不知道两个 X 的长度。因此我的中间符号将不再位于中间......

S -> X0X | X1X | e

X -> 10X | 01X | 1 | 0

不好，w可以从0开始到1结束并且长度可以是偶数

我没有想法......

Answer 1

直接就是以下语法

S -> 0X0 | 1Y1 | e
X -> 0X0 | 0X1 | 1X0 | 1X1 | 0
Y -> 0Y0 | 0Y1 | 1Y0 | 1Y1 | 1

即单词的第一个字符决定您是否进入

X

或

Y

。

X

始终具有奇数个任意字符，中间的字符是

0

。

Y

或多或少相同，只是中间的字符是

1

。

我并不是说这是最基本的语法，但它应该可以解决问题......