8

回文以外の文字列を生成する CFG が必要です。解決策が提供されており、以下のとおりです。 (計算理論の紹介 - Sipser)

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

この文法がどのように機能するかについての一般的なアイデアが得られます。これは、 production を通じて、対応する等しくないアルファベットをどちらかの半分に持つ部分文字列の挿入を義務付け、S -> aTb | bTa回文が決して生成されないようにします。

私が理解しているように、最初の 2 つのプロダクションのセマンティクスを書き留めておきます。

  • S最初と最後のアルファベットが等しくないため、回文にならない文字列を生成します
  • RS回文にならないことを保証する部分文字列として少なくとも 1 つで構成されます。

3 番目のプロダクション、つまり のセマンティクスが完全にはわかりません。

   T -> XTX | X | <epsilon>
   X -> a | b

私の見方では、T は a と b の任意の組み合わせ、つまり {a, b}* を生成できます。どうしてこうならなかったんだろう

T -> XT | <epsilon>
X -> a | b

2つは同等ではありませんか？後者の方がより直感的であるため、なぜ使用されないのですか?

4

5 に答える 5

7

非回文のみを生成する文法を確実に作成する最善の方法は、次のとおりです。

  • Pal - 回文の言語
  • {a, b}* - アルファベット {a, b} のすべての文字列を含む言語
  • Non-Pal - 回文ではないすべての文字列の言語 (つまり、Pal にない)

非パル = {a, b}* - パルであるというオブザーバー

Pal の文法は次のように知られています。

  • S -> ラムダ | | | b | アサ | BSb

{a, b}* の文法は次のように記述できます。

  • S -> ラムダ | サ | サ | Sb

non-Pal の文法を構築するには、次のことを確認します。

  • x が非 Pal の要素である場合:
    • axa は non-Pal の要素です
    • bxb は non-Pal の要素です
  • y が {a, b}* の要素である場合:
    • ayb は non-Pal の要素です
    • bya は non-Pal の要素です

このすべての情報を組み合わせると、非 Pal の文法は次のようになります。

  • S -> aSa | bSb | aAb | ばあ
  • A -> ラムダ | あぁ | アブ

これで物事が明確になることを願っています

于 2013-12-08T00:23:40.087 に答える
5

その文法における in の定義はT、確かに不必要な複雑さのようです。はとのT任意の文字列を生成できるため、より単純な定義でも問題ありません。ab

本を書くことのソーセージ工場の性質のために、作品がそのまま与えられていると推測することしかできません。

元の間違った答え:

Xそれ自体が になることはできず<epsilon>、 とTの組み合わせではないため、それらは等価ではaありませんb。T回文 (空の回文、単一の文字、またはペアになっていない中心文字を含む回文を含む) にのみ展開できます。

X空になる可能性がある場合はT、何にでも展開できますが、できません。

ノート

T -> XTXこの答えは、製作者の作品に対する意図は、置換における 2 つの同一の非終端記号が同一の文字列を表さなければならないという仮定に基づいています。私は見るテキストを持っていないので、質問自体によって動機付けられていることを除いて、この仮定が十分に根拠があるかどうかはわかりません. 他の場所でそうでない場合、この仮定は著者による誤りである可能性があります。一般に、この要件は文脈自由文法には当てはまらないと思います。

正しいプロダクションは次のようになります。

R -> aRa | bRb | S
S -> aTb | bTa
T -> aTa | bTb | a | b | <epsilon>
于 2011-06-27T15:32:42.850 に答える
2

非回文のこの定義は非常に直感的であることがわかりました。著者は回文の定義から始めたと思います

R -> aRa | bRb | a | b | <epsilon>

そして今、この定義がどのように「台無し」になるのかと尋ねられました。

つまり、彼は定義を 3 回展開し、1 つずつ交換aRa | bRbしaRb | bRa、残りの生成物を に一般化しました(a|b)R(a|b)。

于 2011-06-28T19:10:20.030 に答える