0

だから私はここで非回文のための文脈自由文法について尋ねている人を見つけました: 非回文の ための文脈自由文法

与えられた CFG は次のとおりです。

R -> XRX | S
S -> aTb | bTa
T -> XTX | X | <epsilon>
X -> a | b

と

R -> aRa | bRb | S
S -> aTb | bTa
T -> aTa | bTb | a | b | <epsilon>

私の質問: 回文ではないにもかかわらず、「aaabba」はこの CFG によって受け入れられないのでしょうか? 次のようなルールがあれば、この CFG はより正確になりますか。

T -> aTa | bTb | aTb | bTa | a | b | <epsilon>

上記の最後の行の代わりに？それとも私は何かを誤解していますか？:<

4

1 に答える 1

0

1つ目は問題ありませんが、2つ目はそうではありません。

最初のものの場合、シーケンスは次のとおりです。

R -> XRX -> aRa -> aSa -> aaTba -> aaXTXba -> aaaTbba -> aaabba.

2番目のものはすべての非回文を生成できないと言っているのは正しいと思います。

于 2013-03-11T01:30:00.597 に答える