問題タブ [dcg-semicontext]

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

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

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

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

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

長いシーケンスと短いシーケンスの間の距離は、短いシーケンスと短いシーケンスと同じ長さの長いシーケンスの任意のサブシーケンスとの間の最小距離です。

私が使用している距離は、マンハッタン距離だと思います。（ただし、距離関数を変更できるようにしたいので、これは重要ではありません）。

この最初のバージョンは、早期放棄のない素朴な実装を示しています。同じ長さのすべてのサブシーケンスを生成し、これらをマップしてそれらと短いシーケンスの間の距離を見つけ、aggregate/3 を使用して最小値を見つけます。

クエリの例:

この次のバージョンは、長いシーケンスのサブシーケンスと短いシーケンスの間の距離が既に見つかった最小値を超えると計算を中止するため、より効率的である必要があります。

クエリ:

しかし、これではアサートとリトラクトを使用しているので、同じアルゴリズムを実行するバージョンが必要ですが、これらはありません。セミコンテキスト表記のdcgでこれを行うことができるはずだと思いますが、把握するのが難しいと思います...バックトラックによって生成しているサブシーケンスを追跡し、同時に最小距離の「状態」を追跡するにはどうすればよいですか今まで見つかった？

私が抱えている問題.. seq_subseq/2 は、バックトラッキングによってサブシーケンスを生成しています。テストされる最初のサブシーケンスは、最小距離に設定する必要があります。次にループしたいので、トラックに戻って別のシーケンスを生成します。しかし、後戻りするには失敗しなければなりません。しかし、次のシーケンスを確認するために、これまでの最小距離を戻すことはできません。

バックトラッキングを使いたくない場合は、サブシーケンスを順番に生成するための状態遷移述語を定義する必要があると思います。

この時点で

だから私は関係を定義する必要があると思います:

それは次のように機能します：

と

しかし、私はこれを効率的な方法で行う必要があります。

更新- Mat からの回答のおかげで、私はこれを手に入れました。これは大きな改善だと思います。誰でもこれに対するさらなる改善を見ることができますか? 私は二重にネストされた -> 構造と ! accumate_dis/4 の定義では、どちらも醜く見えます。また、短いシーケンスから最短距離である長いシーケンスのサブシーケンスを返すようにしました。

非整数で動作する必要があるため、clpfdは適切ではないと思います。

クエリ:

セクション「Type - 1 Grammar」の下のChomsky Classification of Grammarsで説明されているように、Chomsky によって記述された文脈依存言語の要素を生成することに興味があります。

(基本的に、標準の文脈自由文法に似ていますが、ターミナルを含む生産規則の左側に複数の記号を許可します)。

Prolog の定節文法については知っていますが、それらとチョムスキーの文脈依存言語との間の明確なマッピングは見当たりません。DCG フレームワークを使用して、左側に複数の記号を含むプロダクション ルールを記述する「普遍的な」方法はありますか?それとも、個々の言語ごとにアドホックなアプローチが必要ですか?