如何找到该语言的语法？

Question

如何用chomsky求出该语言的语法：La = {ww^r: w e {0,1}^*, w结尾为1}？

这是我的解决方案：

S -> 0S0|1S1| 0|1|E(epsilon)

我可以在这里更改什么或者解决方案是否正确？

Answer 1

短语

通过使用乔姆斯基

不正确。 “乔姆斯基”不是一个可以“使用”的工具或方法。此外，所提出的 CFG 对于该语言来说是不正确的，因为它可以生成奇数长度的字符串，以及

w

以 0 结尾的字符串。以下语法适用于该语言。然而，它不是乔姆斯基范式（CNF）。如果需要，您可以轻松地将其转换为 CNF 语法。

S -> 1S1 | 0S0 | 11

这是 CNF 中的等效语法：

S0 -> XT | YU | XX
S -> XT | YU | XX
T -> SX
U -> SY
X -> 1
Y -> 0