問題タブ [automaton]

ウィキペディアは、決定論的ステート オートメーションは「入力文字列ごとにオートマトンの一意の計算 (または実行) を生成する」と述べています。

一意の文字列を計算するための可能なパスは1つしかないため、これを常に理解していました。その場合、以下は DSM です。

しかし今、私はこれを考え直し、説明を各入力文字列が単一の可能なパスを持ち、そのパスは他のすべての入力文字列から一意であると解釈しています。この場合、'11' と '12' は同じパスをたどるので、以下は DSM ではありません。

私の質問は、次は DSM または NDSM ですか?

オートマトン理論の割り当てを行っています。これは、決定論的有限オートマトンの遷移関数によって単語が受け入れられるかどうかを判断する必要があります

私はこの入力ファイルを持っています:

入力は 4 つの整数で始まり、最初はオートマトンの状態の数、次はオートマトンの遷移の数、3 番目の数は初期状態、そして最終状態の数です。次に、最終状態が続きます (この例では、最終状態は 2 と 5 です)。

次に、N 行 (N は遷移の数) が続き、それぞれに 2 つの整数と文字 I、J、および C があり、遷移、つまり遷移が状態 i から状態 J に文字 C で移行する状態を表します。この行に続いて、テストする文字列の数を含む単一の整数 S が続き、次にそれぞれの文字列を含む S 行が続きます。

このプログラムの出力は次のようになります。

文字列が受け入れられたか拒否されたかを示す必要があります。これまでのところ、入力を使用して作業をコーディングしただけです。

オートマトンを表現するのに最も便利な方法がわかりません。単純に配列を使用する必要がありますか? 配列にどのようなロジックを適用しますか? オートマトンのアルファベットを事前に知らずにそれを行う方法はありますか? オートマトンを表現するためにデータ構造が必要ですか?. 私はこの割り当てに少し行き詰まっており、いくつかのアイデア、いくつかの疑似コード、またはそれを行うためのアイデアが欲しいです。コードは別の言語ですか？私は自分の課題をやりたいので、解決策を望んでいませんが、何か助けがあれば

この投稿で説明するように、非決定性有限オートマトンをシミュレートするための割り当てを行っています。この入力をファイルから読み取らせますtarea4.in：

入力の最初の行は整数Tで、プログラムを評価するケースの数を表します。各テストケースは4つの整数で始まり、最初はオートマトンの状態の数、次はオートマトンの遷移の数、3番目の数は初期状態、そして最後の状態の数です。次に、最終状態が発生します（この例では、最終状態は2と5です）。次に、Eが最終状態であることを表す整数Eを持つF行が来ます。

次に、N行（Nは遷移の数）が来ます。それぞれ2つの整数と、遷移、つまり遷移が状態iから状態Jに文字Cで進む状態を表す文字I、J、およびCがあります。この行の後には、テストする文字列の数を含む単一の整数Sが続き、次にそれぞれの文字列を含むS行が続きます。

期待される出力は次のとおりです。

私のコードに帰着する出力：

これが私のコードです：

私の質問は：なぜ私は間違った出力を得るのですか？テストケースで定義されたオートマトンの非決定性のためだと思いますが、文字列を正しく評価するにはどうすればよいですか？呼び出された関数evaluate_stringを何らかの方法で変更して、非決定論によって文字列を評価するためにオートマトンを使用できるさまざまなパスを確認するにはどうすればよいですか？

私はこれに数日間立ち往生していて、正直に言うと私はやや必死です。

数日間、非決定性有限オートマトン (NFA)、より具体的には文字列認識機能をシミュレートするプログラムを作成しようとしています。何度か失敗した後、ユーザーKonrad Rudolphのおかげで、次の疑似コードに基づいたソリューションを実装できました。

NFA では、現在の状態のセットがあり、各ステップで現在のすべての状態を調べ、それぞれについて、すべての有効な遷移を選択します。これらの結合されたセットは、新しい状態セットを形成します。

最後に、現在の状態と受け入れ状態の交差が空でないかどうかを確認します。

擬似コードでは、これは次のようになります。

これは、1 行ずつ C++ コードに変換できます。彼はこれを簡単にすることを勧めました。std::set<int> for the current and next sets

C ++での私の実装は次のとおりです。

私はこの入力を持っています：

予想される出力は次のとおりです。

ただし、私のコードは出力として生成されます。

テスト ケースの最後の文字列では、プログラムは何もせず、実行を停止しません。私の質問は、この特定の入力でプログラムがクラッシュするのはなぜですか。JFlapで同じオートマトン NFA を設計し、この最後の入力を認識します

あくどどど

.

コードの実装でどのような間違いがありますか?

Haskellで有限オートマトンを表現する良い方法は何ですか？そのデータ型はどのようになりますか？

私たちの大学では、オートマトンは5タプルとして定義されていました

ここで、Qはオートマトンの状態のセット、Xはアルファベット（この部分は必要です）、deltaは（Q、X）から2タプルを取得し、状態/ -s（非決定論的バージョン）を返す遷移関数です。 Fは、受け入れ/終了状態のセットです。

最も重要なのは、どのタイプが必要かわからないことですdelta...

私は2つのオートマトンの合成を行っています（実際にはトランスデューサーです）。それで、その時点で、それを視覚的に表現して分析したいと思います。

同じための最良のツール/ライブラリはどれですか？

人々は私にドットとgraphvizを提案しました。どちらが良いですか？私はOCamlでコードを書いています。それを描くためのライブラリはありますか？

これは私が描きたいトランスデューサーの例ですか？

テスト結果の形式として TAP(Test Anything Protocol) を使用しようとしています。ただし、テスト結果に添付する必要があるログ ファイルがいくつかあります。これを達成するための良い習慣を探しています。

たとえば、tap ファイルと 2 つのログ ファイル (a.log、b.log) があります。

このタップファイルにログファイルの内容を挿入する良い方法はありますか? ありがとう。

オートマトンが決定論的であるかどうかを返すモジュールを数学で作りたい。同じ状態で始まり、同じシンボルを読み取る2つの遷移がある場合、または空の遷移が存在する場合、オートマトンは決定論的ではないと考えています。

このコードをデバッグしたいのですが、できません：

Aはオートマトンで、最初の要素は状態のリスト、2番目はアルファベット、3番目は遷移、4番目は初期状態、5番目は最終状態のリストです。

主な問題は、関数をAに適用すると、関数が終了しないことです。

編集：解決済み

これが最終的なコードです。

私は学生で、プログラミング コースでは Haskell を学ぶ必要があります。だから私はそれが初めてで、それほど多くの経験がありません。また、フォーラムに質問を投稿することに慣れていません。

そのため、まずライブラリを投稿します。一緒に作業する必要があります。(DA : 決定論的オートマトン)

toDA 関数は、リスト表現でオートマトンを取得し、それをオートマトンに変換します。この機能とライブラリの残りの部分は、講義の議長によって与えられます。

問題は、型の関数を書くことです

この関数は、オートマトン、状態、および文字列を受け取り、文字列を読み取った後にオートマトンの状態を返します。

これまでのところ、アイデアは明確です。タイプ DA のオートマトンは、状態遷移関数デルタを持っています。したがって、関数「advance」は、何らかの方法でそのデルタ関数を呼び出す必要があります。しかし、型に統合された関数にアクセスするにはどうすればよいでしょうか?

私はいくつかの方法でこの問題に取り組もうとしましたが、いくつかの場所を調べても答えがありませんでした。質問は次のとおりです。

[質問]
2 つの正規言語 (有限記述言語 idk と呼ばれる場合があります) と が与えられた場合L1、L2新しい言語を次のように定義します。

を使用して表示することになってL is regularいますが、次の制限があります。

• Equivalence クラスを使用する必要があり、他に方法はありません

• Rank(L)同等クラスの数に制限を表示するように使用できません。代わりに、それらを表示する必要があります

• すべての通常の言語が保持する Closure プロパティを使用できます

私は完全な証明を期待しているわけではありませんが (それはありがたいです)、そのようなことを行う方法についての説明です。
前もって感謝します。