State machine (状態機械)

状態機械はアルゴリズムを設計するために使われる数学の抽象化です。状態機械は一連の入力を読み、入力に基づき、異なる状態に変えます。

状態は、状態遷移の実行を待っているシステムの状況を表します。状態遷移は条件を満たすか、イベントを受け取ったときに実行する一連のアクションです。状態遷移図では、円はそれぞれのありうる状態を表し、矢印は状態遷移を表します。

最終状態を見れば、その状態に至るまでの一連の入力について何らかの手がかりが得られます。

２種類の基本的な状態機械について:

• 決定性有限オートマトン

  • このタイプでは、入力に対して遷移できるのは 1 つだけです。これは「if」文（statement）に似ており、「if x then doThis else doThat」のような記述はできません。コンピューターは 2 つの選択肢のうちいずれかを実行しなければなりません。

• 非決定性有限オートマトン

  • ある状態が与えられた場合、入力によって複数の異なる状態に遷移する可能性があります。

図 1: 決定性有限オートマトン

図 1 では、状態は状態 1 から始まります。状態は入力 'X' が与えられれば状態 2 に変わり、入力 'Y' が与えられれば状態 3 に変わります。

図 2: 非決定性有限オートマトン。

図 2 において、入力 'X' が与えられた場合、状態は状態 1 のまま変わらないか、状態 2 に変わる。

regular expression は状態機械として表すことができることに注意してください。