Clever Geek Handbook

コンピューティングの理論。 ステートマシンの概要

ネタバレ
すぐに説明しますが、あまり正式には説明しません。



有限状態マシン



これは、有限数の状態を持つ単純化されたコンピューターモデルであり、理解の容易さ、推論の容易さ、ソフトウェアまたはハードウェアの実装の容易さの代わりに、RAM、読み取り専用メモリー、I / Oデバイス、プロセッサーコアなどのコンピューターのすべての機能を犠牲にします。



宇宙船を使用すると、正規表現、字句解析プログラム、ゲーム内のAIなどを実装できます。



有限状態マシンには、遷移テーブル 、 マシンの現在の状態 、 開始状態 、および最終状態があります。



遷移表 -現在の状態と入力シンボルの遷移はそこに保存されます。 最も単純な実装は、2次元配列のようなものです。



例1
  • 水平方向の上部には、入力可能な文字があります。
  • 垂直の左は現在可能な状態です。


画像



ここで、状態0から状態1までは、入力文字「a」がある場合にのみ取得可能であり、文字が「b」の場合は状態1から状態2までであることがわかります。



現在の状態は、マシンが特定の時間に存在できる状態のセットです。



開始状態は、宇宙船が作業を開始する状態です。



最終状態は、マシンが特定の文字列を受け入れる状態のセットであり、そうでない場合は拒否します。



決定論的有限オートマトン（決定論的有限オートマトン）



現在の瞬間に1つの状態が存在する最も単純な宇宙船には、決定論があります。



決定性 -すべての状態に対して、可能な入力シンボルに対して最大かつ少なくとも1つのルールがあります。つまり、たとえば、状態1に対しては、同じ入力シンボルで2つの遷移はありません。



例2
画像

DFAの遷移図、例1の視覚化を次に示します。状態3が最終です。 この図は、DFAが一連の文字「a」、「b」、「c」がある場合にのみ文字列を受け入れることを示しています。



非決定性有限オートマトン（非決定性有限オートマトン）



NCAはDCAを大幅に改善したものではなく、 自由な遷移 、 非決定論、および状態のセットという形で、いわゆる構文糖を追加しただけです。 これは、状態、入力シンボル、および次の状態が保存される構造で構成される配列として実装できます。



NCAの実装 
//    : _, _, _. struct state { unsigned char current; signed char sym; // signed,      -1. unsigned char next; }; //       2 struct state machine[] = { {0, 'a', 1}, {1, 'a', 1}, {2, 'a', 1}, {1, 'b', 2}, {2, 'c', 3} };




フリートランジション（イプシロントランジション）は、入力シンボルを読み取らずに作成できるトランジションです。



非決定性 -任意の状態の1つのシンボルのゼロ以上の遷移。



多くの状態 -ある時点で、NQAは複数の状態になります。



例3
最終状態は二重丸で示されます。



画像



開始状態では、現在の状態は{1}であり、入力文字 'b'を使用すると、状態1および状態2に移動できます。つまり、入力文字 'b'の後に現在の状態はセット{1、2}です。

例4
自由遷移は破線で示されています。



画像



ここでは、開始状態からの2つの自由な遷移を見ることができます。つまり、入力シンボルを読み取ることなく、すぐに設定状態{2、4}になります。



NKAをDKAに変換するには 、 トンプソンアルゴリズムが使用されます。

NFAをDFAに変換する場合、完全に最小ではないDFAを取得でき、Brzhozovskyアルゴリズムを使用してそれを最小化できます。



ストアメモリを備えたステートマシン（プッシュダウンオートマトン）



これは同じKAですが、スタック形式のメモリが追加されています。 ここで、移行を行うには、スタックから削除する必要があるキャラクターとスタックに追加する必要があるキャラクターのいくつかの要因を考慮する必要があります 。



CAMPは、プログラミング言語の解析や数式の括弧のカウントなど、添付ファイルの数に制限がない場所で使用できます。 もちろん、可能な状態の数はスタックとは異なるため、宇宙船を使用して実装することは不可能です（メモリも有限であることを理解しています）。



スタックからキャラクターを削除する -どの遷移でも、どのキャラクターをポップアウトするかが決定され、スタックの一番上にそのようなキャラクターがなければ、ポップアウトしません。 また、キャラクターをスタックに残す必要がある場合は、追加するキャラクターとともに追加されます。



スタックにキャラクターを追加する -どんな遷移でも、スタックに追加するキャラクターを決定します。



タイプ ：





例5
パターン：input_symbol; 削除する文字/追加する文字。 スタックの最後に$記号が追加され、終了した時点を把握できます。



画像



このCAMPは、スタックに文字を追加および削除することにより、ブラケットのネストをカウントします。



DUMPはNAMPと同等ではないため、1つを別のものに変換することは不可能であるため、NAMPはDAMPより優れています。



チューリングマシン



既存のマシンの中で最も強力なマシンであり、他のテープよりも優れているため、好きなように作業できます。 無料の移行はありません。 KA、KAMPなどの他のマシンを解釈できます。



テープは1次元の配列であり、セルの上にヘッドがあるためデータを書き込むことができ、入力データを事前に入力できます。



実施例6
テンプレート：read_character_of_head / written_character; head_offset側。 テープの端は「_」で示されます。



画像



このMTは2進数のインクリメントを実行します。ヘッドは左側にあり、テープが始まります。



実行：



  1. 状態1でゼロが読み取られる場合は、ユニットを書き留めて、右に移動して状態2に進みます。
  2. 状態1にあり、ユニットが読み取られている場合、ゼロを書き留め、左に移動して状態1に進みます。
  3. 状態1で空のボックスが読み取られている場合は、ユニットを書き留めて、右に移動して状態2に進みます。
  4. 状態2にあり、ゼロが読み取られている場合は、ゼロを書き留めて右に移動し、状態2のままにします。
  5. 状態2にあり、ユニットが読み取られている場合、ユニットを書き留め、右に移動して状態2のままにします。
  6. 状態2にあり、空の四角を読んでいる場合、空の四角を書き留め、左に移動して状態3に進みます。


DMTはNMTと同等であるため、違いもありません。



汎用チューリングマシン



入力テープでマシンデータを受信することにより、他のチューリングマシンを生成できるマシン。



欠点 ：



  1. 生成されたマシンのメモリは、UMT自体のメモリより大きくすることはできません。
  2. テープのデータは同じテープ上にあるため、生成されたマシンとUMTの間でテープのスペースを正しく分割できる必要があります。


これで機械の紹介が完了しました;これで、さらに資料を自分で学習できます。



参照：





More articles:


All Articles