えーと-質問が言ったこと。それは私がよく耳にすることですが、私はまだそれを調査することに取り掛かっていません。
（更新）私は定義を調べることができました...しかし、なぜ（@eriksonによって指摘されたように）あなたの実際の経験と逸話への洞察を得ないのですか？コミュニティWikiは、人々が最も洞察に満ちた答えに投票するのに役立ちます。これまでのところ興味深い読書、ありがとう！
3554 次
12 に答える
13
簡単に言えば、これは（量子状態/確率分布とは対照的に）具体的な状態でシステムを表現するために使用できる手法です。
ウィキペディアの記事を引用：
有限状態マシン (FSM) または有限状態オートマトン (複数: オートマトン) または単に状態マシンは、有限数の状態、それらの状態間の遷移、およびアクションで構成される動作のモデルです。有限状態マシンは、プリミティブな内部メモリを備えたマシンの抽象モデルです。
それで、それはあなたにとって何を意味しますか？簡単に言えば、関心のあるシステムの開始状態から終了状態へのパスを表す効果的な方法です。かなり理解しやすい例として正規表現を使用して、パターン AB+C を見てみましょう (そのプラスが上付き文字であると想像してください)。このパターンでは、「ABC」、「ABBC」、「ABBBC」などの文字列を受け入れることを期待しています。先頭に A、末尾に C、途中にいくつかの B (1 以上) があります。 .
考えてみれば、これは絵で考えたほうがわかりやすいです。テキストでそれを偽造すると (そして、私の括弧はループバック アークです)、A (左側) が開始状態であり、C (右側) が右側の終了状態であることがわかります。
_
( )
A --> B --> C
FSA から、チューリング マシンの土地に向かうことで、計算の複雑さへの旅を続けることができます。
ただし、ステート マシンを使用して実際の動作やシステムを表現することもできます。私の世界では、それらを使用して、状態の順序の間違いを非常に許容しないコンポーネントを操作する実際の人々の特定のワークフローをモデル化しています。たとえば、「A は C の前に発生した方がよいでしょう。そうしないと、非常に深刻な問題が発生します。今はそれを不可能にしてください。」
于 2008-12-12T21:44:29.047 に答える
9
あなたはそれを調べることができましたが、一体何ですか。直観的に、有限状態オートマトンは、有限数の状態と、状態から状態に移動できるルールを持つものの抽象化です。状態とは、真または偽のステートメントを作成できるものであり、ルールとは、ある状態から別の状態に変更する方法です。たとえば、「私は家にいます」と「私は仕事中です」という 2 つの状態と、「仕事に行く」と「家に帰る」という 2 つのルールを持つことができます。
このような機械を数学的に見ると、できることとできないことがわかります。正規表現は基本的に、状態が異なる文字列のセットである有限状態マシンを記述する方法であり、ルールは次の文字の読み取りに基づいて状態から状態に移動します。あなたはそれを証明することができます。しかし、式の中の括弧が一致しているかどうかを判断できる有限状態機械がないことも証明できます (FSA のポンピング補題を使用)。
FSA について学ぶべき理由は、FSA を使用して、文字列の照合、システムの制御、ビジネス プロセスの記述、デジタル回路の設計など、多くの問題を解決できるからです。また、本質的にきれいです。
正式には、FSA は代数構造F = ⟨Σ, S, s 0 , F, δ⟩ここで、Σは入力アルファベット、S は状態の集合、s 0 ∈ Sは特定の開始状態、F ⊆ Sは受容状態の集合δ:S×Σ → Sは状態遷移関数.
于 2008-12-12T21:46:53.020 に答える
6
OOP 用語: 特定のイベントで呼び出すメソッドを持つオブジェクトと、以前の呼び出しに応じて異なる動作をするいくつかの (他の) メソッドがある場合....驚き! あなたはステートマシンを持っています！
理論を知っていれば、すべてを再考する必要はありません。あなたは単に「簡単に言えば、それは単なるステートマシンです」と言って、それを実装し続けます。
理論がわからない場合は、しばらく考えて、巧妙なハックを書いて、説明や文書化が難しいものを手に入れましょう...説明する言葉がないからです。
于 2008-12-12T21:58:01.297 に答える
2
上記の良い答え。FSA は主に思考ツールであり、プログラミング手法ではないことを付け加えておきます。それらを便利にするのは、それらが優れた特性を持っていることであり、そのように機能するものはすべてそれらの特性を持っています. 何かを FSA と考えることができれば、それを構築する方法はたくさんあります。
正規表現として
状態遷移表として
while-switch-on-state ループとして
goto-netとして（恐ろしい！）
単純な構造化プログラム コードとして
などなど
誰かが何かが FSA であると言った場合、それがどのように構築されていても、彼らが何について話しているのかすぐにわかります。
于 2008-12-12T22:01:14.317 に答える
2
通常の「反復思考」アプローチでは厄介で複雑なコードが生成されるような、特定の種類の問題に対する優れたツールであるため、すべてのプログラマーはそれらについて知っておく必要があります。
典型的な例はゲーム AI で、NPC はプレイヤーの位置に応じて変化するさまざまな状態を持ちます。たとえば、次のようになります。
- NPC_STATE_IDLE
- NPC_STATE_ALERT (100 メートル未満のプレイヤー)
- NPC_STATE_ENGAGE (プレイヤーがNPCを攻撃)
- NPC_STATE_FLEE (体力が少ない)
FSM は遷移を簡単に記述でき、FSM が記述しているシステムについて複雑な推論を実行するのに役立ちます。
于 2008-12-12T21:44:37.330 に答える
2
操作を完了する前にスレッドを解放する必要がある場合は常に、ステート マシンが必要です。
多くの場合、Web サービスはステートフルではないため、通常は Web サービスでこれを確認することはありません。各 URL がコード内の単一のパスに対応するように URL を再配置します。
別の考え方として、すべての Web サーバーは FSM であり、状態情報が URL に保持されていると考えることもできます。
入力を処理するときによく見かけます。入力がすべて完了する前にスレッドを解放する必要があるため、「入力中」などのフラグを設定します。完了したら、フラグを「入力待ち」に設定します。そのフラグが状態モニターです。
多くの場合、FSM は変数をオンにする switch ステートメントとして実装されます。各ケースは異なる状態です。ケースの最後に、状態を新しい値に設定できます。これはどこかで見たことがあるはずです。
FSM の良いところは、状態をコードではなくデータの一部にできることです。データベースに 1000 項目を入力する必要があるとします。受信データは 1000 個のアイテムの 1 つに対応しますが、通常、操作を完了するのに十分なデータがありません。
FSM がないと、処理を完了して結果を DB に書き込むことができるように、残りのデータを待機する数百のスレッドが存在する可能性があります。FSM では、状態を DB に書き込み、スレッドを終了します。次回受信データを確認できるときは、スレッドから状態を読み取ると、実行するコードを決定するのに十分な情報が得られます。
ほぼすべての FSM 操作は、専用のスレッドを使用して実行できますが、おそらくそうではありません (複雑さは状態の数に基づいて倍増しますが、ステート マシンでは複雑さの増加はより直線的です)。また、概念的な設計上の問題もあります。状態レベルでコードを調べる方が、コード行レベルで調べるよりもはるかに簡単な場合があります。
于 2008-12-12T21:52:37.453 に答える
2
重要: あなたが「ビジュアル」スタイルの学習者である場合は、今行っていることをすべてやめて、このリンクにアクセスしてください... 今すぐ。
あなたが「視覚的な」学習者であれば、非常にアクセスしやすい紹介を提供する優れたリンクがあります.
すでに回答を承認しているようですが、よくあることですが、新しい概念の「視覚的な」紹介に感謝する場合は、リンクをチェックしてください。それは単に優れています。
(注: このリンクは、正規表現のコンテキストでの DFA と NDFA の説明へのリンクを示しています -- アニメーション化されたインタラクティブな図を使用)
于 2009-01-03T18:52:25.773 に答える
1
はい！あなたはそれを調べることができます！
于 2008-12-12T21:28:50.357 に答える
1
これまで言及されていない項目の 1 つは、有限状態オートマトンと正規表現の意味的等価性です。正規表現は有限状態オートマトンにコンパイルでき (これが正規表現ライブラリの仕組みです)、その逆も可能です。
于 2008-12-12T22:02:02.520 に答える
1
それが何であるかは、他のサイト (Wikipedia など) でより適切に回答されています。すでにかなり広範な回答が存在するためです。
それらを知っておくべき理由: おそらくすでに実装しているからです。
コードに可能な状態の数が制限されており (「有限状態」部分)、何らかの入力/イベントが発生すると (「機械」部分) 別の状態に切り替わるときはいつでも、有限状態マシンを作成したことになります。
これは非常に一般的なツールであり、そのための理論的基礎を知っていること、それについて推論できること、および 2 つの FSM を同じ作業を行う単一の FSM に結合する方法を知っていることは大きな助けになります。
于 2008-12-12T21:49:15.480 に答える
1
FSA は、理解するのに最適なデータ構造です。FSA を実装する必要がある場合は、チョムスキー階層の最も低いレベルの計算の複雑さで作業しているためです。良い例は、単語の形態学 (単語の部分がどのように組み合わされるか) です。この非常に高速な分析フレームワークで、最も深刻なケースでも分析できることを示すために、多くの作業が行われました。Karttunnen と Beesley の PARC での研究を見てみましょう。
FSA は、隠れマルコフ モデルなどの機械学習の概念について学び始めるのにも最適な場所です。多くの点で、問題は同じアイデアと語彙を使用して分解できるからです。
于 2008-12-12T22:00:20.650 に答える
1
FSA (DFA と NFA を含む) は、コンピュータ サイエンスにとって非常に重要であり、多くの分野を含む多くの分野で使用されています。たとえば、音声認識用の隠しマルコフ フィールドや正規表現は、ソフトウェアや NLP (自然言語処理)、AI (ゲーム プログラミング)、ロボット プログラミングなどによって解釈される前に FSA に変換されます。
FSA の欠点の 1 つは、通常は遅く、通常は実装が難しく、コードを読んでいるときに理解または視覚化するのが難しいことです。 FSAの研究。
于 2009-01-03T18:55:44.830 に答える