問題タブ [finite-automata]

私は受け入れるDFAを構築することになっています

{w | wは「aa」と「aaa」以外の単語です}

これは正しい解決策ですか？太線の状態が終了状態になります。

編集

どういうわけか、2つの異なる演習を混ぜ合わせました。修正しました。

編集2

これが修正された解決策です（？）！

私は正規表現を与えられました、そして私はそれをNFAそしてDFAに隠蔽することになっています。正規表現は次のとおりです。

a（b | c）* a | aac * b

次に、トムソンのアルゴリズムを使用してこれをNFAにカバーしました。

これがDFAです。

誰かが私が間違っているか正しいかを私に知らせてください。

このDFAを最小化しようとしています：http：//img145.imageshack.us/img145/3006/dfac.png

これが私の最小化されたDFAです：http：//img195.imageshack.us/img195/4131/mdfa.png

私は正しいですか？ありがとう

PS-これは宿題です。宿題について話し合うことができます。私は答えを求めていません。ステートマシンを扱うのはこれが初めてなので、自分が正しい方向に進んでいるかどうかを知りたいだけです。

CS クラスの McNaughton-Yamada アルゴリズムを使用して DFA を構築する必要があります。問題は、アルゴリズムが補足資料であり、それが正確に何であるかがはっきりしないことです. 正規表現を指定してDFAを見つける方法ですか、それともDFAを見つけて最小化していますか? この件に関する情報が見つからないようです。

クラスで DFA を見つけた後にインストラクターが示した最小化ルーチンは、私たちの本で説明されている「マーク」最小化と何ら変わらないように見えるので、私は混乱しています。

お返事をありがとうございます、

ネイサン

これが正しいフォーラムであるかどうかはよくわかりませんが、理論計算機科学でここに移動することが提案されました...

有限状態機械の典型的なアルファベットのサイズはどれくらいですか？

私は現在、高性能FAライブラリの実装に忙しく、続行する前にいくつかの設計上の考慮事項を検討する必要があります。私の状態空間は2147483 647（Integer.MAX_VALUE）のオーダーになります。これは、一般的でない使用でも十分すぎると思います。さて、残っているのはアルファベットスペースだけです。

アルファベットは通常、表示可能なすべての文字のみで構成されていると想定することにメリットはありますか（この場合、アルファベットをとして保存できるbyteため、非常に優れたパフォーマンスが得られます）。Stringまたは、アルファベットラベルを使用できるように、アルファベット記号をsに変換する必要がありますか？この場合、作成するサイズに応じて、を、またはStringのいずれかに変換するマップを保持する必要があります。intshortbyte

DFAには、次の4つのプロパティが必要です。

• DFAにはN個のノードがあります

• 各ノードには2つの発信遷移があります。

• 各ノードは、他のすべてのノードから到達可能です。

• DFAは、あらゆる可能性から完全に均一なランダム性で選択されます

これは私がこれまでに持っているものです：

1. N個のノードのコレクションから始めます。
2. まだ選択されていないノードを選択します。
3. その出力を他の2つのランダムに選択されたノードに接続します
4. 一方の遷移1ともう一方の遷移0にラベルを付けます。
5. すべてのノードが選択されていない限り、2に進みます。
6. 着信接続のないノードがあるかどうかを確認します。
7. その場合、複数の着信接続があるノードから着信接続を盗みます。
8. 着信接続のないノードがない場合を除いて、6に進みます

ただし、これはアルゴリズムが正しくありません。ノード1の2つの接続がノード2（およびその逆）に接続され、ノード3の2つの接続がノード4（およびその逆）に接続されているグラフを考えてみます。それは次のようなものです：

1 <==> 2

3 <==> 4

ここで、<==>とは、双方向の2つの発信接続を意味します（つまり、合計4つの接続）。これは2つのクリークを形成しているように見えます。つまり、すべての州が他のすべての州から到達できるわけではありません。

誰かがアルゴリズムを完了する方法を知っていますか？または、誰かが別のアルゴリズムを知っていますか？二分木を使ってこれを構築できることを漠然と思い出しているようですが、それについてはよくわかりません。

メタクラスの存在と使用により、クラス作成プロセスの洗練されたハンドルが提供されるため、多くのコード作成から解放されることがわかりました。これをアプリケーションで使用します。そこでは、複数の相互作用するサーバーがインスタンス化されます。詳しく説明するには:

各デバイスは、その操作に固有のサーバー クラスをインスタンス化します。これは、最終的にこの 1 つのクラスのサブクラス (のサブクラス) ですBaseServer。現在、一部のデバイス サーバーには が必要であり、一部のデバイス サーバーには(module: )ThreadedTCPserverが必要です。を使用すると の動作がオーバーライドされるため、それらをすべて同じクラスから派生させることはできません。SimpleTCPServersocketserverThreadingMixinSimpleTCPServer

この動的なクラス構成を処理するためにMetaServerType、BaseServer の基本クラスを as(SimpleTCPServer,)または asとして選択する を作成しました(ThreadedTCPServer,)--> 動的に構成されたサーバー クラスの望ましい結果を生成します! (ウーフー)

ここで質問があります。パラメータが保存されている構成ファイルを使用したいと考えています。これらのパラメータは、MetaServerType によってデフォルトで使用されます。例: config.default_loglevel、または config.default_handler など。また、メタクラスの仕様に従って、(コマンドラインまたはその他の方法で) 個々のサーバーをオーバーライドできます。

プログラム フローを介して渡される構成オブジェクトのインスタンスを 1 つだけ持つことは、良い設計方法ですか? これを行う 1 つの方法は、メタクラスのクラス本体で構成オブジェクトを初期化することですが、私のプログラム フローは別の場所で開始されます。これは、メタクラスが数回呼び出され、構成のさまざまなインスタンスが生成されることを意味します。インポート時にメタクラスが呼び出されているようです(?)

したがって、詳細な回答は大歓迎です：

1. メタクラスに構成情報を提供するにはどうすればよいですか?
2. 単一の構成インスタンスをプログラム フローに渡し、編集、更新、そしておそらく最終的に書き込む良い方法は何ですか?
3. メタクラスへの入力引数を何らかの形で拡張できますMetaclass.__new__(meta, name, bases, attrs)か?
   4. おまけの質問: これにより、(インスタンスではなく) 状態を「一時停止」または「再開」できるように、(サーバーの) 有限状態マシンに一歩近づきますか?

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

回路は次のとおりです。

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

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

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

正規表現の非決定論的有限状態オートマトンへの変換について質問があります。

（a * | b *）*をNFAに変換します。私の試みは次のとおりです。

私は完全にマークから外れていますか？またはいくらかそこに？

NBE=>ε

相互に比較した場合、DFAとNFAの両方の相対的な長所と短所は何ですか？

DFAはNFAよりも実装が簡単であり、NFAはDFAよりも受け入れ状態に到達するのが遅いことを知っていますが、他に明確でよく知られている長所/短所はありますか？