スポンサーリンク

決定性有限オートマトンを組んでみた ~状態と動作を結び付ける~

お久しぶりの更新です。ところで、前置きは、映画を観に行って”オートマトン”ってのを連想したからプログラムを組んでみましたって話です。ここからはただの雑談みたいな感じになってるんで、興味のない方は次の節まで飛ばしてくださいませ~。

最近、といっても先月の話ですが、ヴァイオレット・エヴァーガーデンってアニメの映画を観に行ってきました。個人的に好きな作品だったもんで。

知ってる方も多いかと思いますが、一応どんな作品かを説明しときます。

その作品の中では”自動手記人形”というものが存在してまして、それは声を認識して、自動で文字に起こしてくれるという便利な機械の名前です。作中では人が営む代筆業のことも、その自動手記人形の名前を取って”ドール”と呼ばれていました。

戦争しか知らなかった少女がいたのですが、戦争の最中、親のように育ててくれた人と離れ離れになってしまい、保護された先でドールとして仕事をしていくことを決めます。敵を殺すこと、上官の命令遂行を絶対として育ってきた彼女が、ドールという職業を通して何をどう経験して、どんな成長をしていくのかを描いた作品になってます。

って感じです。まぁ、作品について僕の拙い説明を並べ立てたところで無意味なんで本題に入ります(僕の文才の無さが浮き彫りになるのはいいとしても、そのせいで作品を誤解されるのは嫌なんで)。

先ほどの説明の中で”自動手記人形”というものが出てきましたが、そこからオートマトンを思い出したんです。自動と人形といえばオートマトンみたいな感じで。それで組んでみて、せっかくなんで記事にしてみました。

というわけで、雑談にお付き合いくださってありがとうございました。ここから本編です。

スポンサーリンク

オートマトンとは?

さっきから”オートマトン”という単語が出てきてますが、知らない人からしてみれば、何のことやらさっぱりわからないと思うんで説明します。

ざっくりと、めちゃくちゃ単純で機能が制限されまくったコンピュータと思ってもらえればいいかと思います。

オートマトンは日本語にすると”状態機械”となります。オートマトンが、内部状態に応じて処理を変えるので、そういう名前になってるんだろうと思います。

どういうことかと言うと、オートマトンは2つの要素から出来てて、内部状態というものと各内部状態に応じた処理という2つから出来てます(厳密には違いますが、この記事の話を理解する上ではとりあえずそう思っていただければいいかと思います)。

オートマトンは人間からの入力を受け付けて動作するもので、その入力に応じて内部状態を変化させていきます。この内部状態の変化のことを「遷移」と言います。そして、どのように遷移するかは、その時の内部状態とユーザーからの入力によって決まります。

この内部状態と遷移と入力の組み合わせを図で表したものが状態遷移図と呼ばれるものになります。具体例は、書くのが面倒なのでGoogle検索をしてみてください。色々と見つかると思います。

よく自動販売機が例として使われていたので、この記事のプログラムでも自動販売機っぽいものをオートマトンとして組んでみました。実際の自動販売機はどうなっているのかは知りませんが。

今回は自動販売機を例に説明していきますが、オートマトンを適用できるのは自動販売機だけでなく、「人間からの動作を受けて内部状態(ひいては動作)を変更する」という形式を見つけ出せれば大体のものに適用できます。なので意外といろんなところで使えたりします。例えば、ファイルの検索機能とかゲームのキャラの動作なんかもオートマトンの性質を利用すれば楽に実装できたりします。

というのが、オートマトンのざっくりとした説明になります。

とりあえず「オートマトンは人間からの入力によって「処理」と紐づけられた「状態」というものを変えていくものなんだな」と思っておいてください。

次のプログラムで、そんなもんかなぁってくらいには納得していただけるかと思います。

プログラム

上の説明を愚直にプログラム化したものが下のプログラムになります。エラー処理とかは全く考えてないので、あまりいじめないであげてください。

今回もMSYS2でg++を使ってビルドしたので、VS Codeとかだと動かない可能性がありますがご了承ください。

実装は、他にも色々な方法がありますので、ここに書いているプログラムはあくまで実装方法の一例です。例えば、以前の記事で紹介したラムダ式を使えばもっとスマートに書けます。ですが、今回はあくまでも解説することが目的で、こうした方が説明とプログラムとの対応が分かりやすいだろうと思ったので、あまり美しくはないコードになっています。

/********************************
*
* 単純なオートマトン
*
* 仕様
* ・ユーザーからの入力に応じて、現在の状態を返す
* ・自動販売機のシミュレーションを行う
*   0 : 十円玉を入れる
*   1 : 百円玉を入れる
*   2 : ボタンを押す
*   3 : プログラムを終了する
*
*********************************/

#include <iostream>

// プロトタイプ宣言
int NextState( int, int );
void DisplayState( int );
void TransitionBehavior( int, int );
void Behavior0( int );
void Behavior1( int );
void Behavior2( int );
void Behavior3( int );
void Behavior4( int );
void Behavior5( int );
void Behavior6( int );
void Behavior7( int );
void Behavior8( int );
void Behavior9( int );
void Behavior10( int );

int main()
{
  int action;    // ユーザーの行動
  int current_state = 0;

  while(1)
  {
    /* 現在の状態を表示する */
    DisplayState( current_state );

    /* 状態を認識した上で、ユーザーは入力する */
    // 一文字入力
    std::cout << "0 : 十円玉を入れる\n1 : 百円玉を入れる\n2 : ボタンを押す\n3 : 自動販売機を壊す" << std::endl;
    std::cout << "<< ";
    std::cin >> action;

    /* 現在の状態とユーザーからの入力に応じて、遷移時の動作を行う */
    TransitionBehavior( current_state, action );

    /* 自動販売機の状態を更新する */
    current_state = NextState(current_state, action);
    if( current_state == -1 ) { std::cout << "急用ができたため自動販売機から立ち去りました" << std::endl; break; }
  }

  return 0;
}

// 次の状態を返すだけの関数
int NextState( int current_state, int action )
{
  // 二次元配列は左の列から順に、ユーザーの入力 10円投入 100円投入 ボタンを押す プログラム終了 に対応する
  // 行は上から順に、投入金額が0円のとき、10円のとき、・・・、100円以上になったとき、
  int next_state[11][4] = {
    { 1, 10, 0, -1 },   // 0円のときの遷移先
    { 2, 1, 1, -1 },    // 10円のときの・・・以下同文
    { 3, 2, 2, -1 },
    { 4, 3, 3, -1 },
    { 5, 4, 4, -1 },
    { 6, 5, 5, -1 },
    { 7, 6, 6, -1 },
    { 8, 7, 7, -1 },
    { 9, 8, 8, -1 },
    { 10, 9, 9, -1 },
    { 10, 10, 0, -1 }
  };

  return next_state[current_state][action];
}

// 現在の状態と入力に応じて適切な動作を行う
void DisplayState( int current )
{
std::cout << std::endl;
  std::cout << "現在の状態:" << current << std::endl;
  // 各状態(に対応するcase)は投入金額を表す
  // 状態毎に、投入金額の表示と、その状態になった入力によって(actionによって)適切な動作を行う
  switch( current )
  {
    case 0:
      // 状態0での動作(入ってきたときの動作)
      // 金額表示
      std::cout << "現在の投入金額:0円" << std::endl;

      break;

    case 1:
      std::cout << "現在の投入金額:10円" << std::endl;
      break;

    case 2:
      std::cout << "現在の投入金額:20円" << std::endl;
      break;

    case 3:
      std::cout << "現在の投入金額:30円" << std::endl;
      break;

    case 4:
      std::cout << "現在の投入金額:40円" << std::endl;
      break;

    case 5:
      std::cout << "現在の投入金額:50円" << std::endl;
      break;

    case 6:
      std::cout << "現在の投入金額:60円" << std::endl;
      break;

    case 7:
      std::cout << "現在の投入金額:70円" << std::endl;
      break;

    case 8:
      std::cout << "現在の投入金額:80円" << std::endl;
      break;

    case 9:
      std::cout << "現在の投入金額:90円" << std::endl;
      break;

    case 10:
      std::cout << "現在の投入金額:100円" << std::endl;
      break;
  }
}

void TransitionBehavior( int current, int action )
{
  switch ( current ) {
    case 0:
      Behavior0( action );
      break;
    case 1:
      Behavior1( action );
      break;
    case 2:
      Behavior2( action );
      break;
    case 3:
      Behavior3( action );
      break;
    case 4:
      Behavior4( action );
      break;
    case 5:
      Behavior5( action );
      break;
    case 6:
      Behavior6( action );
      break;
    case 7:
      Behavior7( action );
      break;
    case 8:
      Behavior8( action );
      break;
    case 9:
      Behavior9( action );
      break;
    case 10:
      Behavior10( action );
      break;
    default:
      std::cout << "バグと見せかけといてぇ・・・\nバグなんだな~" << std::endl;
  }
}

// 状態0から遷移するときに行う動作
void Behavior0( int action )
{
  switch ( action ) {
    case 2:
      std::cout << ">> 金額が足りません" << std::endl;
      break;
    default:
      break;
  }
}

// 状態1から遷移するときに行う動作
void Behavior1( int action )
{
  switch ( action ) {
    case 1:
      std::cout << ">> 100円" << std::endl;
      break;
    case 2:
      std::cout << ">> 金額が足りません" << std::endl;
      break;
    default:
      break;
  }
}

// 状態2から遷移するときに行う動作
void Behavior2( int action )
{
  switch ( action ) {
    case 1:
      std::cout << ">> 100円" << std::endl;
      break;
    case 2:
      std::cout << ">> 金額が足りません" << std::endl;
      break;
    default:
      break;
  }
}

// 状態3から遷移するときに行う動作
void Behavior3( int action )
{
  switch ( action ) {
    case 1:
      std::cout << ">> 100円" << std::endl;
      break;
    case 2:
      std::cout << ">> 金額が足りません" << std::endl;
      break;
    default:
      break;
  }
}

// 状態4から遷移するときに行う動作
void Behavior4( int action )
{
  switch ( action ) {
    case 1:
      std::cout << ">> 100円" << std::endl;
      break;
    case 2:
      std::cout << ">> 金額が足りません" << std::endl;
      break;
    default:
      break;
  }
}

// 状態5から遷移するときに行う動作
void Behavior5( int action )
{
  switch ( action ) {
    case 1:
      std::cout << ">> 100円" << std::endl;
      break;
    case 2:
      std::cout << ">> 金額が足りません" << std::endl;
      break;
    default:
      break;
  }
}

// 状態6から遷移するときに行う動作
void Behavior6( int action )
{
  switch ( action ) {
    case 1:
      std::cout << ">> 100円" << std::endl;
      break;
    case 2:
      std::cout << ">> 金額が足りません" << std::endl;
      break;
    default:
      break;
  }
}

// 状態7から遷移するときに行う動作
void Behavior7( int action )
{
  switch ( action ) {
    case 1:
      std::cout << ">> 100円" << std::endl;
      break;
    case 2:
      std::cout << ">> 金額が足りません" << std::endl;
      break;
    default:
      break;
  }
}

// 状態8から遷移するときに行う動作
void Behavior8( int action )
{
  switch ( action ) {
    case 1:
      std::cout << ">> 100円" << std::endl;
      break;
    case 2:
      std::cout << ">> 金額が足りません" << std::endl;
      break;
    default:
      break;
  }
}

// 状態9から遷移するときに行う動作
void Behavior9( int action )
{
  switch ( action ) {
    case 1:
      std::cout << ">> 100円" << std::endl;
      break;
    case 2:
      std::cout << ">> 金額が足りません" << std::endl;
      break;
    default:
      break;
  }
}

// 状態10から遷移するときに行う動作
void Behavior10( int action )
{
  switch ( action ) {
    case 0:
      std::cout << ">> 10円" << std::endl;
      break;
    case 1:
      std::cout << ">> 100円" << std::endl;
      break;
    case 2:
      std::cout << ">> 選ばれたのは綾鷹でした" << std::endl;
      break;
    default:
      break;
  }
}

実行結果は次のような感じになります。

現在の状態:0
現在の投入金額:0円
0 : 十円玉を入れる
1 : 百円玉を入れる
2 : ボタンを押す
3 : 自動販売機を壊す
<< 1

現在の状態:10
現在の投入金額:100円
0 : 十円玉を入れる
1 : 百円玉を入れる
2 : ボタンを押す
3 : 自動販売機を壊す
<< 2
>> 選ばれたのは綾鷹でした

現在の状態:0
現在の投入金額:0円
0 : 十円玉を入れる
1 : 百円玉を入れる
2 : ボタンを押す
3 : 自動販売機を壊す
<< 3
急用ができたため自動販売機から立ち去りました

プログラムの説明

上記のオートマトンについての説明とプログラム内のコメントを読んでもらえば理解できるような気もしますが一応説明の方を。

まず、プログラム全体の構成です。次のような感じになっています。

  1. 状態表示
  2. ユーザー入力
  3. 状態とユーザー入力に対応した動作
  4. 状態の遷移

そして、この1番から4番をループさせています。実際の自動販売機を操作するときと、大体似たような流れになっているのではないでしょうか。

1の状態表示は、switch-case文で状態に応じた文を出力しています。

2は何の変哲もない(?)coutとcinです。

3も1のときと同じように、switch-case文で適切な動作をさせています。ただ、ここでの”動作”は現在のオートマトンの状態とユーザーの入力という2つによって決まってくるので、まずオートマトンの状態で分岐して、その次にユーザーの入力によってもう一度分岐しています。

4はcurrent_stateの変更で実現しています。NextState関数の中で、現在の状態とユーザーの入力の組み合わせに対して、正しい遷移先を選び取っています。状態と入力が配列のインデックスになっていて、その組み合わせが与えられたら、配列の要素として格納されている正しい遷移先が返されるという形式になっています。

P.S. この記事で興味を持っていただけたら、是非、ヴァイオレット・エヴァーガーデンの方もご覧ください。

タイトルとURLをコピーしました