今回は、コンピュータサイエンスの基礎の一部を勉強します。
もちろん、全部のコースではありません ただ、「計算の理論」の一部です。
この科目は、有限オートマトンの設計についてです。
すべての用語は、さらにその先で説明します。
では、やってみましょう。
Pythonのステートマシンとは？
ステートマシンは、オブジェクトがイベントに応答してどのように動作するかを定義する動作モデルです。
Pythonでは、ステートマシンは通常、有限状態マシン（FSM）として実装されます。
FSMは計算の数学的モデルであり、デジタル論理回路やコンピュータプログラムの設計に使用されることがあります。
FSMは、状態、状態間の遷移、および遷移時に実行されるアクションのセットで構成されます。
有限状態マシン（FSM）は、デジタル論理回路やコンピュータプログラムの設計に使用できる計算の数学的モデルです。
有限状態機械は、状態、状態間の遷移、遷移時に実行される動作のセットで構成される。
FSMは、状態をノード、遷移をエッジとする有向グラフで表現することができる。
エッジには遷移の引き金となるイベントが書き込まれ、アクションはエッジに関連づけられる。
TOCとオートマタとは？
オートマトン理論とTOCは、どちらも機械の挙動を研究するために用いられるが、そのアプローチは異なる。
オートマトン理論が抽象的な機械そのものに注目するのに対し、TOCはその機械を使って解くことができる問題に注目します。
オートマトン理論とは、抽象的な機械やオートマトンを研究し、それを使って解くことができる計算問題を研究する学問です。
また、オートマトンは形式言語の計算モデルとして用いられることが多いため、オートマトン理論は形式言語理論とも密接な関係がある。
計算理論（TOC）は、アルゴリズムとその効率の研究を扱う数学の一分野です。
アルゴリズムの設計と解析、データ構造、複雑性理論に関係します。
計算理論とは、基本的な入力と出力に基づいて動作するいくつかの仮想マシンを設計するトピックです。
計算の基本は、一定の長さの文字列を受け入れることから始まる。
このような機械の基本的な命名法はオートマトン（Automata）です。
オートマタには2つのタイプがある。
-
- 決定論的有限オートマトン(DFA)。
- 非決定論的有限オートマトン(NDFA)。
決定論的有限オートマトン(DFA)の理解
決定論的有限オートマトン(DFA)は有限状態機械の一種で、決定論的アルゴリズムに基づいて入力文字列と呼ばれる記号の列を受け入れたり拒否したりする機械です。
DFAは有向グラフで表現され、状態はノード、遷移はエッジとして表現される。
エッジには遷移の引き金となるイベントがラベル付けされ、アクションはエッジと関連付けられる。
非決定論的有限オートマトン(NDFA)の理解
非決定性有限オートマトン(NDFA)は、非決定性アルゴリズムに基づいて入力文字列を受理または拒否できる有限状態機械の特殊なタイプです。
NDFAは有向グラフで表現され、状態はノード、遷移はエッジとして表現される。
エッジには遷移の引き金となる事象がラベル付けされ、アクションはエッジに関連付けられる。
基本的なオートマトンは5つのユニットのタプルです。
Automata = (Q, F, δ, q0, Σ)
|
- Q = すべての状態の集合
- F = すべての最終状態の集合。
δ = 各入力による状態の移動を写像する遷移関数または写像関数。
q0 = 初期状態。 - Σ＝入力記号の有限集合。
基本的なDFAの図
pip install python-statemachine
|
この機械は文字列 “aa “を受け付ける。
この図は、DFAを最も単純に表現したものです。
そのパラメータを理解しよう。
- ここでQ = {q0, q1, q2}. 最終状態の集合です。
- q0 は初期状態です。
- q2 は最終状態
- Σ = {a} は全入力記号の集合です。
この機械はq0, q1, q2の3つの状態から構成される。
最初は、ある状態に入力を与えると、別の状態に遷移／移動します。
遷移関数(δ)はこれらすべての活動を記録している。
そして、目的の文字列が特定の状態に到達したとき、その状態をその機械の最終状態と定義します。
Pythonを使ったステートマシンの構築
Pythonを使って自作のState Machineをプログラミングします。
これは、Paperに描くのと同じことです。
また、いくつかの特殊な操作で遷移を確認する予定です。
1. statemachineライブラリのインストール
コマンドプロンプトを開き、pipコマンドを入力します。
from statemachine import StateMachine, State
class LightBulb(StateMachine):
# creating states
offState = State("off", initial = True)
onState = State("on")
# transitions of the state
switchOn = offState.to(onState)
switchOff = onState.to(offState)
bulb = LightBulb()
print(bulb.current_state)
|
State('off', identifier='offState', value='offState', initial=True)
|
ステートマシンの動的なプロパティ
ステートマシンを作成すると、モジュールはそのマシンに存在する各状態のためのプロパティの特別なセットを作成します。
インスタンスとプロパティを使用して、そのプロパティがその状態に対して機能しているかどうかを確認することができます。
上記のコードでは、そのような状態が2つあります。
そのため、作成されたプロパティもTrueになっています。
プロパティを確認するコード
bulb.is_offState # returns True
bulb.is_onState # returns False
|
この記事もチェック：Pythonでのディレクトリの作成、取得、削除、存在の確認の方法を解説する
状態数、遷移数の確認
Stateクラスから遷移と全状態を引き出す方法を見てみましょう。
クラスが2つの状態しか持たない場合、この方法はあまり役に立たないように見えるかもしれません。
しかし、複数の状態を持つクラスを考えてみると、このテクニックが役に立つことがわかるだろう。
状態の数をチェックするコード
オートマトンでは、現在のすべての状態を記録しておく必要がある。
そのために、次のようなリスト内包を使う。
a = [s.identifier for s in bulb.states]
print(a)
|
結果は、以下の通りになります。
['offState', 'onState']
|
説明
- リスト内包を使って、すべての状態をリストに格納します。
- そして、”identifier “属性を使って、for a loopを実行します。
- states属性を用いて各状態を取得します。LightBulbクラスのインスタンスであるbulbオブジェクトを使用して、これを呼び出す必要があります。
-
- このリストを変数「a」に代入します。
-
- 次に、それをプリントします。すべての状態を取得することができます。
遷移を確認するコード
オートマトンは常にある状態から別の状態へ遷移します。
これを簡単に言うと遷移と呼ぶ。
そこで、StateMachineは遷移を記録するためにtransitions属性を持っている。
b = [s.identifier for s in bulb.transitions]
print(b)
|
結果は、以下の通りになります。
['switchOff', 'switchOn']
|
このように、StateMachineのコードはすべてStatesのものと同じです。
ただ、transitionsというキーワードをbulbオブジェクトと一緒に使うだけです。
まとめ
このように、Pythonを使って簡単なステートマシンを構築することができます。
ステートマシンは、AIアルゴリズムやゲームを設計する際に勉強すべき重要な概念の1つです。
また、ロジックを構築する際にも、ステートマシンは良いトピックになります。
というわけで、このトピックを終わります。