6

規則が左側に、非終端記号の右側に 1 つ (または複数) の終端記号を持つことを許可する、文脈自由文法への次の拡張を検討してください。つまり、次の形式の規則です。

A b -> ...

右辺は、文脈自由文法のように、何でもかまいません。特に、右側が最後にまったく同じ終端記号を持つ必要はありません。その場合、この拡張機能は状況依存になります。しかし、端末は単なるコンテキストではありません。時々、この端末は「プッシュバック」と呼ばれます。

明らかに、これはもはや CFG (タイプ 2) ではありません。1型を含みます。しかし、それは何ですか？本当にもう0型？

この特定の拡張は、Prologの Definite Clause Grammars (誤解を避けるために、ここでは Prolog の完全な拡張を考慮しません。つまり、端子は有限のアルファベットに由来し、恣意的な項ではないと仮定します。また、DCG で許可されている Prolog の追加の引数も考慮しません。すでに 0 です。)

編集: 拡張機能を説明する簡単な方法を次に示します: フォームの CFG ルールに追加します。

A b -> <epsilon>
4

3 に答える 3

5

ここに部分的な答えがあります：

文法はタイプ 0 内にあります。文脈依存文法 (タイプ 1) にはwAx -> wBx、w と x が終端記号と非終端記号の文字列であり、B が空でない形式の規則があります。B は空ではないので、|wAx| <= |wBx|. あなたの文法にはAx -> z、z が終端記号と非終端記号の文字列であり、空にすることができ、x を削除できる形式の規則があります。これは、CSG の 2 つの原則に違反しています。

残念なことに、私は次の 2 つのことに答えませんでした。

  • あなたの文法によって生成された言語はタイプ 1 ですか? 文法はタイプ 0 ですが、それは言語がタイプ 1 ではないという意味ではありません。たとえば、通常の言語 (タイプ 3) は CFG (タイプ 2) で記述できます。

  • 言語は再帰的ですか? これは重要です。そうであれば、言語は決定可能である (停止問題に悩まされない) からです。

    私は現在、2 番目の点の証明を試みていますが、おそらく私の能力を超えています。

于 2012-08-22T16:44:03.323 に答える
3

Prolog の DCG フォーマリズムに関する私の質問に答えるために、この拡張機能はセミコンテキストと呼ばれるようになりました。DCG の N253 DIN ドラフト 2014-04-08 - ISO/IEC WDTR 13211-3:2014-04-08を参照してください。

与えられた

a1, [b] --> ... .

a2, [b,b] --> ... .

terminal-sequence[b]は、 terminal-sequence と同様にセミコンテキストになりました[b,b]。

同じ終端シーケンスがルールの最後に表示される場合、コンテキストは次のようになります。

a3, [b,b] --> ..., [b,b].

したがって、「半」はここでは「半分」を意味します。群の代数的性質の半分が保持される半群に似ています。

于 2014-06-12T12:08:50.720 に答える
1

はい、0型だと思います。最初の 3 種類 (3、2、1) の原則は、還元を実行できないことです。これらは生成専用タイプです。

ここでは、端末をイプシロンに変換して、タイプ 0 にすることができます。

于 2012-08-22T16:36:11.307 に答える