reverse - 文脈自由文法と反転

Question

この言語を生成するために文脈自由文法を設計しています:

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

最初の 2 つの文字列を次のように定義します。

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

そして、それらを組み合わせます：

S -> UV

しかし、その逆を文脈自由文法としてどのように表現すればよいのでしょうか?

Answer 1

文法の文脈自由を利用する必要があります（これまでに提示しているのは、単なる正規文法です）。

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

「ababa」や「aabaa」などと一致しますが、「aabba」とは一致しません。

これをニーズに合わせて変更するのはあなたに任せますが、指定した言語はu空の文字列である可能性があるため、ですべての文字列を生成することに注意してください{a,b}*。