reverse - 上下文无关语法和反转

Question

我正在设计一种上下文无关的语法来生成这种语言：

{ w in {a,b}* | w is of the form uvu^R, where u and v are any strings in {a,b}* }

我将前两个字符串定义为：

U -> aU | bU | _
V -> aV | bV | _

然后结合这些：

S -> UV

但是我如何将反转表达为上下文无关语法呢？

Answer 1

您需要利用语法的上下文无关性（到目前为止您所呈现的只是常规语法）：

U-> aUa | bUb | a | b | _

将匹配“ababa”和“aabaa”之类的内容，但不匹配“aabba”。

我会留给您根据您的需要进行更改 - 但请记住，您指定的语言有可能u是空字符串，因此它会生成{a,b}*.