問題タブ [fsm]

私は、高性能の有限状態マシンを実装する Java ライブラリの作成を開始しようとしています。たくさんのライブラリがあることは知っていますが、ほとんどすべてのライブラリが一度に 1 つだけを処理するように最適化されたオートマトンを構築するため、ゼロから独自のライブラリを作成したいと考えています。

ステート マシンの設計に手を出した SO コミュニティの人々が、このような高性能ライブラリの実装に関して最も重要で最良の設計原則をどのように感じているかを知りたいです。

考慮事項

1. 生成されるオートマトンは通常、大規模ではありません。(~ 100-500 州)。
2. ただし、実装はスケーリングできる必要があります。
3. 実装は、高速変換(最小化、決定化など) を有効にする必要があります。
4. DFA、NFA、GNFA、PDA、およびおそらくツリー オートマトンの実装を検討しています。可能であれば、単一のインターフェースの下でうまくいけば。
5. メモリ使用量とパフォーマンスのバランスが取れている必要があります。

現時点でのデザインに関する現在の質問は次のとおりです。

1. State、SymbolおよびのクラスをTransition定義する必要がありますか? または、「隠された」内部構造を使用する必要があります。個人的には、クラスをそのまま使用すると、同じ情報をより凝縮された形式で格納できるため、多くのメモリが浪費されると感じています。しかし、これはより速い変換を可能にしますか? 他に長所/短所はありますか？

2. データを内部に保存する最良の方法は何ですか? HashMapおよびのようなデータ構造を使用するとHashSet、償却された一定時間のルックアップが可能になりますが、関連するオーバーヘッドの要素があります。これが最善の方法ですか？遷移情報をプリミティブ (またはそうでない) 配列として保存すると、かなりの量のメモリが浪費されるようです。特に、ライブラリが一度に多くのオートマトンを処理する必要がある場合。異なるデータ構造の長所と短所は何ですか?

ご意見をお待ちしております。ありがとう！

ムーア オートマトンに関するウィキペディアの記事では、クロックされたデジタル回路はムーア オートマトンの一種であると言われています。

http://en.wikipedia.org/wiki/Moore_machine#Mechanism

how about the other way around. how is an arbitrary moore automaton implementet in digital electronics, are there any rules how to build the circuit. or is this never done? just wondering...

Verilog モジュールで状態を変更するために以下が使用されるのを見てきました。

state <= 2'b10;

state <= #1 IDLE;

= だけでなく <= が使用されるのはなぜですか? ＃1を使用する目的は何ですか？違いはありますか？

最初に使用された FSM を示す Verilog コードを次に示します。2番目に置き換えても同じように機能しますか？

この回路用に 2 つの状態を持つミーリー​​ マシンを描きましたが、ムーア マシンの状態図を描くことができません。これを行う方法がわかりません。

回路は次のとおりです。

この回路は、1 つのバイナリ入力 X と 1 つのバイナリ出力 Y を持つムーア マシンです。出力 Y は、最新の 2 つのクロック パルスでサンプリングされた X の 2 つの値に依存します。Y は常に、これら 2 つの入力値の XOR 結合の結果である必要があります。

つまり、基本的に、状態が 1 で入力が 1 の場合は 0 になります。状態が 1 で入力が 1 の場合は 1 になります。状態の反対である限り、1 になります。 .

これは状態図でどのように表されますか? 遷移表はどうですか？

FTDIUSB-シリアルデバイスを介して画像を受信した後に画像をフィルタリングするシステムをVHDLで作成することを検討しています。その一環として、CPLDが存在する必要のある状態を特定したと思いますが、VHDLで複雑なステートマシンを作成したことがないため、メソッドが適切かどうか疑問に思っています。現在、私のステートマシンの基本的な概要は次のとおりです。

ここでの私の問題は、すべてのステートマシンのチュートリアルで、すべての立ち上がりエッジ（または同様の、ただしクロックごとに1回）で状態の変化を見つけることができ、このデバイスはIDLEに多く存在し、USB_RXFNがローになったときにのみNEGOTIATINGに移行する必要があることです。それが完了するまで交渉を続け、画像全体が転送されるまで受信を続けます。

私のアプローチに根本的な欠陥はありますか？CPLDは単にこの目的には適していませんか？または、複数のクロックの間状態を維持することは可能であり、チュートリアルは単純化のためにそのように書かれていますか？

VHDL で有限状態マシンを実装しているかどうか、すべての出力が可能なすべての状態にあることを述べる必要があるかどうか疑問に思っていますか? 一部の出力が 1 つの状態から別の状態に変化しないことがわかっていて、状態の順序も同じ順序になることがわかっていても?

たとえば、この (強制) 例では:

私の理解では、これを行わないとラッチが作成されますか?

そのような例では大したことではありませんが、10 を超える出力と 10 を超えるステートを持つマシンを使用している場合、VHDL ファイルが信じられないほど乱雑に見え始めます。何度も同じこと。これを行うより良い方法はありますか？

編集:出力の「デフォルト」状態を定義できますか? IE は、すべてのプロセスの外側で b を 1 に設定し、それが 0 である case ステートメントでのみ定義します。それはうまくいくでしょうか？

ミーリー マシンがあり、大きな文字列がある場合、ミーリー マシンがその文字列を生成できるかどうかを確認するにはどうすればよいですか?

ミーリーマシンを正規表現に変換することを考えましたが、その方法も明確ではありません。

ありがとうございました。

私の最初の状態であるerlanggen_fsmがあります：

で、〜がある：

Testしかし、私はシェルでメモを見ていません

新しい状態にどれだけ正しく移行しますか？

この素晴らしいサイトの人々のおかげで、ほぼ完全で機能するコードをまとめることができました。最後に 1 つ質問があります。

コードは次のとおりです。

遷移関数 find-next-state に問題があります。着信文字をテストし、これに基づいて fsm が最終状態に達したときに true 値を返すか、そうでないときに false 値を返すように定義するにはどうすればよいですか?

ご回答ありがとうございます。

アップデート：

ご回答ありがとうございます。コードがわかりにくくて申し訳ありません。トランジションの定義を修正したところ、次のようになりました。

しかし今、遷移関数を定義しようとしています。固定遷移文字がなく、char-alphabetic を使用したときは? と char-numeric?、これらのコード行は魔法のように機能しました:

しかし、fsm-trans の状態の新しい定義を使用するには、何を変更すればよいでしょうか? このコードを DrScheme に入力すると、((second (first trl)) ch)) という行のエラーが表示されます。

今後ともよろしくお願いいたします。

私はUMLに不慣れで、FSMダイアグラムをリグレードし、同じ状態につながる2つの遷移を表す方法を説明します。たとえば、私はstate1にいます。

つまり、state1からstate2に2本の線を引く必要がありますか？