問題タブ [cyk]

したがって、次の形式で与えられる 1 次元配列内に文法があります。

例：

これは次のように翻訳されます。

------

その他の例:

また、array.number は [0, 9] で囲まれています。

array.right と array.left は区間 [A, Z] のリテラルです。

startStringという入力文字列からstopStringという別の入力文字列に取得するために適用されるすべてのルール (文法コンポーネント) を含むリンク リストを返す必要があります。

ご覧のとおり、この文法はチョムスキー正規形で与えられていません。文法が変更され、プログラムから要求されたリンク リストを返すことができないため、CNF に変換できないと思います。

どのように進めればよいですか？Post-Scriptum と同じように、文法内には最大で 1000 のそのようなルールがあるため、再帰パーサーは適していない可能性があると思います。以前に尋ねたことがありますが、CYK アルゴリズムについて読むように言われました。これは私がプロジェクトとして与えられた問題です。このレベルのプログラミングを始めたばかりであることを覚えておいてください。とはいえ、基本的な知識はすべて持っています。

それらは同じ概念だと思い ます https://courses.engr.illinois.edu/cs498jh/Slides/Lecture10.pdf 確率的 CYK アルゴリズムがビタビ アルゴリズムを使用して解析されますが、私の概念は正しいですか?

私は現在、一連のプロダクションが与えられた後に CYK 解析テーブルを生成する Prolog プログラムに取り組んでいます。ただし、2 つの行をチェックしてそれらが等しいかどうかを確認するのに問題があります。これが私がこれまでに持っているものです：

入力が次のようであるとしましょう:

私の問題は、リストの最大長に相当する変数を作成し、毎回デクリメントする方法を見つける必要があることだと思いますが、sublist_check の初期長を元の数に戻すというエラーが発生します。

どんな入力/フィードバックでも素晴らしいでしょう、どうもありがとう!

えーと、

私は ocaml と CYK テーブルを通じて関数型プログラミングを学ぼうとしているので、 List.mem や命令型関数はありません。私の目的は、2 つのセルの製品を形成することです。

これが私が現在持っているものです：

予想される出力は次のようになります。

私の考えたプロセスは、基本的にリストをループして各文字列を別のリストの各文字列に配置する一連の再帰関数を作成することでした。

私のエラーは、特にappend_funcでの追加方法だと思います。より適切な質問は、文字列のリストを作成する方法かもしれないと思います。