文脈自由文法と逆転

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 | _ 

は「アベバ」のようなものにマッチしますと " aabaa "ではなく" aabba "である。

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