この記事は、 Brotherofkenによって作成、コンパイル、およびコンパイルされています。 どうもありがとうございます。

前の記事では、この記事をできるだけ明確にするために、すべての基本的な定義と原則を述べようとしました。 すべてが適合しなかったので、これらのファイルに精通することを強くお勧めします。

Basis 、 Basis2 、最小化。 この記事の後半では、説明文をイタリック体で残しました。

この記事では、抽象オートマトンとは何か、どのように表現されるかをアクセス可能な言語で説明します。オートマトンの理論は数学に満ちていて複雑なので、私は人間の言語で書いて、準備のできていない読者が危機にwhatしているものを理解できるようにします。

電子デジタル回路は、正式には2つのクラスに分類できます。

組み合わせスキーム（CS）-メモリがありません。出力信号は、固定された時点での入力データの組み合わせに応じて生成されます（信号変換の遅延を考慮に入れます）組み合わせスキーム、そのタイプ、および構築原理は、別の記事のトピックであり、例として、制御バス、マルチプレクサ、デマルチプレクサ、デコーダーおよびエンコーダー、コードコンバーター、組み合わせカウンターおよび加算器など。
メモリを備えたスキーム-操作のアルゴリズムは、入力およびメモリの状態（以前の時点での状態）に依存します。これらのスキームは、有限オートマトンの理論を使用して説明されています。それらについてのスピーチはさらに進みます。

つまり、最初のクラスは入力信号を処理する論理デバイスです。 2番目の要素にはメモリがあり、入力されたデータに応じて信号に応答します。

抽象オートマトン

マシンは、開発者によって設定されるいくつかの機能を実装する必要があります。単純な加算器にすることも、プロセッサのマイクロコマンドを実装したり、RAMから単語を選択したり、式の解析を行ったりすることもできます。

一般的な用語では、詳細に入ることなく、抽象的なオートマトンは次のように表すことができます。

または、図から数学的な説明に移る場合：

A = <A、B、C、δ、λ>

指定：

セット{A}-オートマトンの物理的な入力の値のセットを表します。この場合の入力には、論理的な0と1をエンコードする高電圧レベルと低電圧レベルのシーケンスがあります。
セット{B}-オートマトンの物理出力での値のセットを表します。
セット{C}-およびオートマトンの内部状態を表すセット-メモリ。将来的には、C0はオートマトンの初期状態を示します。
δ= X×Z→Zは、オートマトンの遷移関数であり、状態ajからオートマトンが通過する状態aiを一意に決定します。
λ= X×Z→Yは出力関数であり、入力と内部状態に応じてマシンの出力に何があるかを決定します。

δとλは、視覚的に簡単にするために図には示されていません。

そのようなオートマトンは時間的に離散的に動作します。つまり、オートマトンの入力、出力、および内部状態の値は、離散的な瞬間に変化します。

したがって、抽象オートマトンとは何かを一般的な用語で説明しました。このようなオートマトンの例としては、トリガー、コンピューターレジスタ、または加算器があります。

マシンには2つのタイプがあります。

自動マイル。これは、連立方程式によって記述されます。

c（t）=δ（a（t）、c（t-1））;

b（t）=λ（a（t）、c（t-1））。
ムーア突撃ライフル。次の方程式で説明されます。

c（t）=δ（a（t）、c（t-1））;

b（t）=λ（a（t）、c（t））。

ご覧のように、現在の時間のオートマトンc（t）の状態は、前の時間の状態と入力信号の関数です。

オートマトンは、出力関数のタイプが異なります。 Milesマシンでは、出力信号は入力信号a（t）と時刻c（t-1）の前の瞬間のマシンの状態によって決定されます。ムーアオートマトンの出力信号は、入力信号a（t）と現在の状態c（t）のペアによって決まります。

また、1つのタイプから2番目のタイプへ、およびその逆に渡すことができます。さらに、マイリーオートマトンからムーアオートマトンに渡すとき、オートマトンの内部状態の数は同じままであり、逆遷移では、内部状態の数が増加する可能性があります。必要なタイプのオートマトンを合成（グラフを描画）したと信じて、これについては詳しく説明しません。

それで、これで材料は終わりました。マシンを説明してみましょう。

つまり Milesタイプのマシンは、以前の状態に応じて、入力を変更すると出力信号を生成します。 出力信号の持続時間は、入力の持続時間に依存せず、その存在のみに依存します。 ムーアタイプのマシンでは、出力信号は現在のマシンの状態に依存します。 マシンは、状態が変化するまで特定の出力信号を生成します。

オートマトンを設定する方法

最初の部分でわかったように、オートマトンは、入力アルファベットと出力アルファベットの組み合わせ、遷移と出力を決定する内部状態と関数のセットです。ただし、通常、関数δとλは定義されていないため、オートマトンの動作は異なる方法で説明する必要があります。

オートマトンを指定するには、主に2つの方法があります。

グラフを使用します。
遷移表と出口表を使用します。

カウント

オートマトングラフは、頂点がオートマトンの内部状態を象徴する有向接続グラフであり、アークはある状態から別の状態への遷移です。

マイルを数える場合、同様の文字と出力文字が円弧に示されます。出力文字はアーク上に書き込まれ、出力状態が前の瞬間のオートマトンの状態に依存することを象徴しています。

ムーアオートマトンのグラフでは、入力文字のみがアークに書き込まれ、出力文字は頂点の近くに表示されます。

重要なポイント：入力文字と同じ数のアークが各頂点から出てくる場合、オートマトンはcompleteと呼ばれます。つまり、各入力文字の遷移が各頂点から定義されている場合。この例では、ミーリーオートマトンは完全で、ムーアオートマトンは部分的です。

そしてもう1つ：入力文字よりも1つの頂点からのアークが多い場合（つまり、同じ入力文字を持つ2つ以上のアーク）、そのようなオートマトンは非決定的と呼ばれます。これは、形式化された記述を作成するときに発生する可能性があり、決定論的オートマトンへの移行が必要になりますが、常に実行できるとは限りません。また、決定論的オートマトンをすぐに描画することで、このプロセスの説明を見逃しています。

それがグラフのすべてです。

遷移および終了テーブル。

グラフは人にとってより明確であり、表は機械のためです。どのマシンも、遷移と出力のテーブル（TPV）の形式で表すことができます。 TPVでは、行はオートマトンの内部状態であり、列は入力文字です。

マイルとムーアのカウント用にTPVを構築します。入力文字または出力文字が定義されていない場合は、代わりにダッシュが使用されます。状態が定義されていない場合、この同じ単純なルールが適用されます。

TPVカウントマイル

TPVマイルでは、遷移と出力が各セルに記録されます。たとえば、マシンが状態C0で、文字a1が入力に到着すると、状態C1になり、文字b3が出力に表示されます。

TPVカウントムーア

ムーア伯爵の場合、マークされた遷移表が作成されます。出力文字の追加の列が強調表示されます。

入力文字の下のセルでは、マシンがどの状態になるか、右端のセル-返される出力文字が書き込まれます。

自動合成の例

抽象オートマトンの助けを借りて、ほとんど何でも記述できます。デジタル回路の動作を記述したり、パーサーまたは字句解析器を記述したりできます。トリガーを説明してみましょう-オートマトンはなぜですか？

グラフを設定するには、トリガーアルゴリズムの言葉による説明が必要です。私たちは読みます：

入力および出力アルファベットをエンコードします。

A = {a0、a1}。ここで、a0は入力Rで論理1、a1は入力Sで論理ユニットです。

B = {b0、b1}。ここで、b0はQの出力の論理値0、b1はQの出力の論理単位です。

オートマトンマイルのグラフを作成します。