問題タブ [automata]

トランジション グラフを最小化するプログラムを作成しようとしています (基本的には状態と同様の数値を組み合わせています)。基本的に、アルゴリズムは、最初に同じ 'a' と 'b' の入力を持つ状態を見つけて結合し、それらを '残り物' リストから削除してから、'a' または 'b' のいずれかを持つ状態を見つけて結合します。

次に例を示します。

私が直面している問題は、特定の遷移グラフの状態の量に応じて任意の数の組み合わせが存在する可能性があるため、配列をどのように/何をするかを知ることです。これをコーディングする方法についてのアイデアや、すべてを処理する方法についてのアドバイスはありますか?

乾杯

私は DFA を持っていますが、州を受け入れているかどうかわかりません。私はそれが受け入れる正規表現しか知りません。状態を受け入れているかどうかを調べようとしているので、DFA の各状態を調べて、受け入れている正規表現と現在の状態によって生成された単語を比較したいと思います。

そのため、単語を正規表現と比較して一致するかどうかを教えてくれるものを探しているので、DFA のこの状態を承認済みの状態としてマークし、別の状態に移ることができます。私はいくつかのアルゴリズムを実装しようとしていましたが、それは私にとって非常に複雑な問題であることが判明しました. これについて教えてもらえますか？ありがとう！

アルファベット: {a,b,c}

正規表現の例: ab.(a|c)*

それについて肯定的なものを見つけることができません。そして、イプシロン遷移を伴うNFAはイプシロン-NFAですか？ありがとう。

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

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

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

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

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

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

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

DFAを検討してください：

δ（A、01）は何に等しくなりますか？ オプション：

正解はオプションB）ですが、方法がわかりません。誰かがそれを解決するための手順を説明してください。また、一般的に、DFAと移行のためにどのように解決するのですか？

ありがとう。

まだ C# は初めてなので、よろしくお願いします :)

これらのプロダクションを配列または表形式のリストに格納する方法は、C# で次のようになります。上記のプロダクションはファイルから読み込まれます。

文脈依存の文法を理解しようとしていて、言語が

1. {ww | w は文字列です}
2. {a ⁿ b ⁿ c ⁿ | a、b、cは記号です}

文脈自由ではありませんが、型指定されていないラムダ計算に似た言語が文脈依存であるかどうかを知りたいです。単純だがおもちゃではない例 (上記のおもちゃの例を考えます) の例を見てみたいと思います。たとえば、記号の文字列がは現在スコープ内にあります (たとえば、関数の本体を生成する場合)。文脈依存文法は、未定義/未宣言/未結合の変数を (セマンティックではなく) 構文エラーにするのに十分強力ですか?

これは私が描いたDFAです-

それが正しいか？の規則に違反する同じ入力シンボルに対して状態の遷移が異なる
ため、私は混乱していますが、他の解決策は考えられません。q42DFA

特定の言語が通常か、文脈自由か、文脈自由でないかを判断するのに助けが必要です。答えには簡単で非公式な説明で十分なので、ポンピング補題を使用する必要はありません。

私が次の言語を持っているとしましょう：

これが私の解決策です：

L2 は無限のメモリを必要としないため、L2 用に DFA を構築できます。したがって、L2 は規則​​的です。L3 については、上記と同じ理由です。L4 の場合、単純に「abc」を受け​​入れないため、通常の DFA を構築できます。

正規言語は ∩ の下で閉じているため、L1 は正規です。

L2 の場合、言語を次のように分割できます。

L3 に対して DFA を構築できることがわかっているため、L3 は正則です。L4 はコンテキストフリーです。スタックを使用して a:s と b:s の数をカウントする PDA を構築できるからです。

正規言語と文脈自由言語の ∩ が文脈自由言語になるため、L2 は文脈自由です。

L3 の場合、スタックが 1 つに制限されているため、コンテキストフリーではないことがわかります。2 つ以上の比較を行うには、より多くのスタックが必要です。

私の推論は正しいですか？もうすぐ試験があり、この背後にあるアイデアが得られたかどうかを知る必要があります.

前もって感謝します

私は現在（自然言語の）コーパスを持っています、そしてこれらはすでにとられたステップです：

1. コーパスを1つの大きなファイルに連結した後、シンボルテーブルを生成しました。

2. このシンボルテーブルを前提として、コーパスをバイナリFSTアーカイブ（FAR）に変換します。

FAR内のすべてのFSTの和集合を取得し、開始状態から最終状態までの最大重みパスを計算したいと思います。シェルからテストするために、これは私がしたことです：

しかし、私は次のエラーに遭遇し続けます：

警告：CompatSymbols：最初のシンボルテーブルは存在しますが、2番目は欠落しています

エラー：ユニオン：1番目の引数の入力/出力シンボルテーブルが2番目の引数の入力/出力シンボルテーブルと一致しません

もちろん、このエラーは、最初にFSTをソートせずに2項演算を実行しようとすると発生します。

FSTを正しくソートしていないと思います、または...シンボルテーブルの使用方法を完全に誤解しています。ユニオン（または、さらに言えば、他の二項演算）がこのように失敗する理由はありますか？