15

有限オートマトンの使用は何ですか？そして、私たちが計算理論で研究するすべての概念。私はまだそれらの使用を見たことがありません。

4

8 に答える 8

32

これらは、コンピュータサイエンスやプログラミングで広く使用されている概念の理論的基盤であり、それらを理解することで、それらの使用方法（およびそれらの制限）をよりよく理解するのに役立ちます。遭遇する必要のある3つの基本的なものは、パワーの昇順です。

  • 正規表現に相当する有限オートマトン。正規表現は、文字列の照合やテキストの抽出のプログラミングで広く使用されています。これらは、基本的な文字、グループ化、および繰り返しを使用して、有効な文字列のセットを記述する簡単な方法です。それらは多くのことを行うことができますが、バランスの取れた括弧のセットと一致させることはできません。
  • プッシュダウンオートマトン。文脈自由文法に相当します。テキスト/入力パーサーとコンパイラーは、正規表現が十分に強力でない場合にこれらを使用します（そして、有限オートマトンの研究で学ぶことの1つは、正規表現ではできないことです。これは、正規表現をいつ作成するかを知るために重要です。より複雑なものを使用する）。文脈自由文法は、文字列を解析する際の特定の時点での有効性が他に何が見られたかに依存しない「言語」（有効な文字列のセット）を記述することができます。
  • 一般的な計算（コンピューターでできることなら何でも）に相当するチューリングマシン。これらをカバーするときに学ぶことのいくつかは、コンピューティング自体の限界を理解することを可能にします。優れた理論コースでは、プログラムを作成することが不可能な問題を特定できる停止性問題について学びます。そのような問題を特定したら、試行をやめる（または可能なものに改良する）ことを知っています。

これらのさまざまなコンピューティングメカニズムの理論と制限を理解することで、問題とプログラムをよりよく理解し、プログラミングについてより深く考えることができます。

約1年前に、フリーランスのコーディング交換サイトの1つで、停止性問題を解決するプログラムを要求する作業要求が公開されました。何人かの人々は、彼らが「要件を理解した」そして「すぐに始めることができる」と言って申し出で応えました。要件を満たすプログラムを作成することは不可能でした。コンピューティング理論を理解することで、公の場でコンピューティングを本当に理解していないことを示す入札者にならないようにすることができます（そして、理解を宣言して申し出をする前に、問題を徹底的に調査する必要はありません）。

于 2009-10-03T20:25:09.803 に答える
4

有限オートマトンは、通信プロトコルや正規表現との文字列の照合に非常に役立ちます。

于 2009-10-03T20:21:09.350 に答える
2

オートマトンは、ハードウェアおよびソフトウェア アプリケーションで使用されます。こちらの実装セクションをお読みくださいhttp://en.wikipedia.org/wiki/Finite-state_machine#Implementation

Automata ベースのプログラミングの概念もあります。これをチェックしてください http://en.wikipedia.org/wiki/Automata-based_programming

乾杯

于 2009-10-03T20:27:14.633 に答える
2

すべての GUI、すべてのワークフローを有限オートマトンとして扱うことができます。各ページは、特定のイベントによって発生する状態と遷移と考えてください。一連の条件が満たされるまで、ワークフローの特定のページまたは次の段階に進むことができない場合があります。

于 2009-10-03T20:27:43.760 に答える
2

有限オートマトンは、例えば形式言語の構文解析に使用されます。これは、有限オートマトンがコンパイラおよびインタープリタ技術の作成に非常に役立つことを意味します。

歴史的に、有限状態マシンは、非常に単純な自動化によって多くの問題を解決できることを示してきました。

于 2009-10-03T20:50:08.940 に答える
1

コンパイラコースを受講してみてください。再帰下降パーサーを実装するために、有限状態オートマトンを使用してコンパイラーまたはインタープリターを作成する可能性が非常に高くなります。

于 2009-10-03T20:21:28.780 に答える
1

たとえば、ライフサイクルが定義されたオブジェクトの状態を管理する場合などです。この例として: 書店での注文。注文には次の状態があります。 -注文済み -支払い済み -発送中 -完了

有限オートマトンのプログラムは、ある状態が他の状態によってどのように変化するかを知っています。

于 2009-10-03T20:28:40.203 に答える
1

有限オートマトンは、ステート マシン (SM) の一種です。一般に、SM は形式言語の解析に使用されます。

文字だけでなく、多くのエンティティを形式言語として使用できます。

そして、正規語は形式言語の一種です。通常の言語を解析するにはどのタイプの SM が適しているかを示すいくつかの理論があります: http://en.wikipedia.org/wiki/Regular_language

于 2009-10-03T20:41:43.577 に答える