🤖

ステートマシンの理論からAWS Step Functionsを理解する

に公開
AWS
Step Functions
StateMachine
状態機械
tech

AWS Step Functionsはステートマシン（状態機械）を構築することができるサービスです。ステートマシンとは計算機科学（CS）で出てくる有名な概念です。この記事では、AWS Step Functions上でステートマシンを実際に構築する流れを解説します。
なお、ステートマシン（状態機械）は有限オートマトンとも呼ばれ、本記事では同じ意味で使います。こちらはすでに有限オートマトンを知っている方向けの説明ですが、ここでの有限オートマトンは決定性であるとします。

ステートマシン（状態機械）の説明

直感的な説明

ステートマシンとは、「複数の状態の間をどう移動するか」を表現する計算モデルです。

具体的な例を考えるとわかりやすいです。最近見かけてすごいと思った車を自動で検知して青になる信号機を例に考えてみます。感応式信号というらしいです。

これが状態遷移図になります。状態遷移図はステートマシンを表した図になります。
ステートマシンの例

信号機の状態は3つあるとします。「Red」「Blue」「RedWait」の3つです。「RedWait」はずっと青であることを禁止するために入れており、青だったら赤で30秒キープすると思ってください。
最初は赤だとします。startの矢印が「Red」に入ってきています。「Red」の状態から車が来ない（no_car）だと「Red」のままです。車が来る（car）と、「Blue」になります。車が来ている間は「Blue」のままで来なくなると「RedWait」になります。「RedWait」になった瞬間に30秒間待つルールがあるとわかりやすいです。「RedWait」から抜けるとき、車が来ていると「Blue」、来ないと「Red」になります。
「青」は車が通れる受理状態となっており、二重丸で表されています。それ以外は車が通ってはダメなので通常の丸になっています。
これがステートマシンです。状態とinputが来たときに、どのように次の状態にいくかのルールが定められています。開始状態があり、受理状態があります。受理状態は複数あっても構いません。
この例だと状態は「Red」「Blue」「RedWait」です。inputとなりうるのは「car」「no_car」の二つで、開始状態が「Red」、受理状態は「Blue」です。

ここに「car, car, no_car, no_car, car, no_car」のinputが来たとします。するとどうなるでしょうか？これは先頭から順に読んでいき、状態が移り変わると思えばよいです。
最初は開始状態の「Red」にいて、そこに「car」のinputが来るので「Blue」に移ります。同様に考えていくと「Blue, RedWait, Red, Blue, RedWait」と移り変わってきます。最終的な状態は「RedWait」にいます。なので最後の状態だと車が通れず受理されません。「このステートマシンはこのinputを受理しない」となります。

「car, no_car, car」などは受理します。このようにinputが与えられたときに、受理するかしないかが決まります。受理するinputの集合を言語といいます。
実は、このステートマシンは、最後が「car」であるようなinputを受理します。それ以外のinputを受理しません。

例をかなり詳しく説明しました。数学的な定義も一応紹介しておきます。ここは飛ばして読んでも理解できるように書いたつもりです。

定義

ステートマシン

ステートマシンは5個組 (Q, \Sigma, \delta, q_0, F) です。

  • Q は 状態 と呼ばれる有限集合
  • \Sigma は アルファベット と呼ばれる有限集合
  • \delta : Q \times \Sigma \to Q は 遷移関数
  • q_0 \in Q は 開始状態
  • F \subseteq Q は 受理状態の集合

先ほどの例に照らし合わせると、

\begin{aligned} & Q = \lbrace \text{Blue}, \text{Red}, \text{RedWait} \rbrace \\ & \Sigma = \lbrace \text{car}, \text{no-car} \rbrace \\ & q_0 = \text{Red} \\ & F = \lbrace \text{Blue} \rbrace \end{aligned}

遷移関数は図を見てください。受理状態は複数あり得るので、集合となっています。
遷移関数ですが、現在の状態とアルファベットの要素が与えられると次の状態が決まります。なのでそのような関数になっています。
アルファベットの列（先ほどの例だと「car, no_car, car」）を文字列といいます。文字列ごとに受理するか受理しないかを先ほどのように状態を追っていき、最後が受理状態になるかどうかで判定します。

言語

ステートマシン M が認識する言語 A = L(M) とは以下のように定義されます。

A = L(M) = \lbrace w \mid w \text{はステートマシンが受理する文字列} \rbrace

先ほどの例だと「car, no_car, car」は言語の要素となります。また、

A = \lbrace w \mid w \text{の最後はcar} \rbrace

となります。

AWS Step Functions

AWS Step Functionsはステートマシンを構築するためのサービスです。

構築するステートマシン

今回構築するステートマシンは、1で始まって0で終わるような0と1からなる文字列を認識するようなステートマシンです。数式で書くと、

L(M) = \lbrace w \mid w \text{は1で始まって0で終わる} \rbrace

このようなステートマシン M が存在するかどうかはまた別の問題になります。今回の場合だと存在して以下のようなステートマシンになります。

構築するDFA

\begin{aligned} & Q = \lbrace q_0, q_1, q_2, q_3 \rbrace \\ & \Sigma = \lbrace 0, 1 \rbrace \\ & q_0 = q_0 \\ & F = \lbrace q_3 \rbrace \end{aligned}

\delta は図を見てください。このようなステートマシンの作り方は、計算理論の基礎 1.オートマトンと言語(共立出版)などを参照してください。

Step Functionsの定義

JSONコード
{
  "Comment": "DFA of 1{0,1}*0",
  "QueryLanguage": "JSONata",
  "StartAt": "Init",
  "States": {
    "Init": {
      "Type": "Pass",
      "Comment": "Initialize index",
      "Assign": {
        "index": 0
      },
      "Next": "q0"
    },

    "q0": {
      "Type": "Choice",
      "Comment": "Start state and not accept state",
      "Choices": [
        {
          "Condition": "{% $index >= $length($states.input.input) %}",
          "Next": "Reject"
        },
        {
          "Condition": "{% $substring($states.input.input, $index, 1) = '0' %}",
          "Assign": { "index": "{% $index + 1 %}" },
          "Next": "q1"
        },
        {
          "Condition": "{% $substring($states.input.input, $index, 1) = '1' %}",
          "Assign": { "index": "{% $index + 1 %}" },
          "Next": "q2"
        }
      ],
      "Default": "Violation"
    },

    "q1": {
      "Type": "Choice",
      "Comment": "Not accept state",
      "Choices": [
        {
          "Condition": "{% $index >= $length($states.input.input) %}",
          "Next": "Reject"
        },
        {
          "Condition": "{% $substring($states.input.input, $index, 1) = '0' %}",
          "Assign": { "index": "{% $index + 1 %}" },
          "Next": "q1"
        },
        {
          "Condition": "{% $substring($states.input.input, $index, 1) = '1' %}",
          "Assign": { "index": "{% $index + 1 %}" },
          "Next": "q1"
        }
      ],
      "Default": "Violation"
    },

    "q2": {
      "Type": "Choice",
      "Comment": "Not accept state",
      "Choices": [
        {
          "Condition": "{% $index >= $length($states.input.input) %}",
          "Next": "Reject"
        },
        {
          "Condition": "{% $substring($states.input.input, $index, 1) = '0' %}",
          "Assign": { "index": "{% $index + 1 %}" },
          "Next": "q3"
        },
        {
          "Condition": "{% $substring($states.input.input, $index, 1) = '1' %}",
          "Assign": { "index": "{% $index + 1 %}" },
          "Next": "q2"
        }
      ],
      "Default": "Violation"
    },

    "q3": {
      "Type": "Choice",
      "Comment": "Accept state",
      "Choices": [
        {
          "Condition": "{% $index >= $length($states.input.input) %}",
          "Next": "Accept"
        },
        {
          "Condition": "{% $substring($states.input.input, $index, 1) = '0' %}",
          "Assign": { "index": "{% $index + 1 %}" },
          "Next": "q3"
        },
        {
          "Condition": "{% $substring($states.input.input, $index, 1) = '1' %}",
          "Assign": { "index": "{% $index + 1 %}" },
          "Next": "q2"
        }
      ],
      "Default": "Violation"
      },

    "Accept": {
      "Type": "Succeed"
    },

    "Reject": {
      "Type": "Fail",
      "Error": "NotAccepted",
      "Cause": "String does not match 1{0,1}*0"
    },

    "Violation": {
      "Type": "Fail",
      "Error": "AlphabetViolation",
      "Cause": "Input contains invalid character (not in {0,1})"
    }
  }
}

ステートマシンを構築しているだけあって、ステートマシンの定義を知っているととても簡単に書くことができます。前処理として文字列の現在のindexを持ちたいので、Init で初期化をします。そのあとはステートマシンをそのまま書き、最終的にAcceptとRejectを判定すればよいです。
具体的には、 q_0, q_1, q_2, q_3 の4状態をまず作成して、それぞれの遷移を書きます。また遷移の一つに「そこで文字列が読み終わる」も加える必要があります。さらに Accept, Reject, Violation の3状態も用意します。これは最終的にどうなるかで、アルファベットにない文字を使ったときのために Violation を用意しています。
ここまでみると、作成するステートマシンの内容さえ頭に入っていれば簡単に構築できます。Step Functionsを構築するときは、先にステートマシンの図を書いておくのがおすすめです。

実行をしてみる

すると以下のように成功します。

これは 1 で始まって 0 で終了する文字列なので成功します。条件を満たさない文字列をinputとすると失敗します。予定通りです。

冷静になる

len(input) > 0 and input[0] == "1" and input[-1] == "0"

終わりに

今回はAWS Step Functionsとは何かをステートマシンの理論から追いかけました。今回構築した例はとても簡単な例でしたが、ステートマシンで表現できるものは幅広く、これらを構築できるAWS Step Functionsはとても便利なサービスです。AWS Lambda Durable Functionsなどの似たサービスが登場していますが、ステートマシンを定義するサービスがStep Functionsだと思っておけばある程度見通しがつくようになるはずです。
ステートマシンの理論自体はとても面白いものです。ぜひ勉強してみるとよいと思います。

GitHubで編集を提案

Discussion