稿
目
次
稿
目
次
問題
大学院の入試問題にこんな問題がありました。
次のように定義されるビット列検出器について、問 1)、2)、3) に答えよ。 ◇入力及び出力はビット列であり、時刻 t(=0,1,2,…) の入力ビットを x(t)、出力ビットを z(t) とす る。ただし、z(0)=z(1)=z(2)=0 とし、3 ≦ t のときは入力ビット列が [x(t-3),x(t-2),x(t-1),x(t)] = [1, 1, 0, 0] または [1, 1, 0, 1] を満たすときに限り z(t)=1 を出力するものとする。例えば '11001101100110' を（左端から）入力すると、出力は '00010001001000' となる。 1) 初期状態 S0 およびその他の状態 S1,S2,S3 からなる状態遷移図を示せ。 2)（省略） 3)（省略）
というわけで早速「出力付き有限オートマトン（順序機械）を書いてみました.。ここで使用した図は Mealy 型です。すなわち、現在の状態に対して入力を与えると次の状態へ移行するとともに出力が得られるというものです。
さて、状態遷移図は描いてみましたが、私はオートマトンとか状態遷移図とかにあまり詳しくありません。果たしてこれがあっているのか間違っているのか・・・。ならばシミュレーションして検証してみよう、というのが今回のお題です。
設計
抽象的な発想
このような問題を解くのにオブジェクト指向は大変有効です。オブジェクト指向では知ってのとおり、データとデータに対する操作を定義します。今回、「状態」をデータに見立て、「入力、遷移、出力」を操作として考えます。
まず、「状態」は
入力0 に対する遷移先と出力 入力1 に対する遷移先と出力
という情報（データ）によってできます。一方、操作は
入力を与えると、遷移先（状態オブジェクト）と出力が得られる。
という関数として定義できます。
具体化
上述の発想から考えられる最も単純な発想は状態ごとにクラスを作成してしまう方法でしょう。つまり「クラス S0」「クラス S1」・・・を作成する方法です。しかしこれは面倒なばかりでなく、技術的な問題もあります。「入力、遷移、出力」を扱う関数を考えた場合、遷移（状態オブジェクト）は S0、S1、S2、S3 のいずれであるかわかりません。したがって、オブジェクト指向の概念から言えば、この関数が S0、S1、S2、S3 を区別なく扱えるようにするために、これらの上に S なる抽象クラスを作らなければならなくなるでしょう。これは面倒なだけでたいした利点もないので今回は別の方法をとります。
そこでクラスを一つだけ作り、状態は後から与えることにします。つまり、クラス S を用意し、そのインスタンス変数として状態オブジェクト S0、S1、S2、S3 を作成し、その後でそれぞれのインスタンスに対して、出力と遷移先（状態オブジェクト）を設定するようにします。遷移先は S0、S1、S2、S3 それぞれのポインタを与えることで表現すればよいでしょう。これを実現するために
入力0 に対する遷移先 入力0 に対する出力 入力1 に対する遷移先 入力1 に対する出力
を保持するメンバ変数が必要です。これらのメンバの値は直接設定してもかまわないのですが、今回は専用の関数を用意します。
さらに、入力（0 or 1）を受け取り、次の遷移先と出力を返す関数を用意します。とはいえ、関数が返せる値はひとつだけですので、引数に次の遷移先と出力を受け取る変数へのポインタをとることにします。遷移先は状態オブジェクト S0、S1、S2、S3 のポインタとして保持されているので、引数でとるのはポインタ変数へのポインタということになります。
(untitled)
上述の「状態」をクラス（State）として実装したのが.です。実験用の main 関数では、各状態を表すオブジェクト s0、s1、s2、s3 を宣言した後に、遷移先と出力を遷移図に従って設定しています。そして現在の状態を指すポインタ cur を用意し、s0 を初期値として設定しています。あとは次々と cur の入力操作関数を呼び出し、cur へ新しい状態を受け取るとともに出力を受け取ります。
#include <iostream>
using namespace std;
class State {
State *next0; // 入力 0 に対する遷移先
int output0; // 入力 0 に対する出力
State *next1; // 入力 1 に対する遷移先
int output1; // 入力 1 に対する出力
public:
// 状態を設定するための関数
void SetState(State *next0, int output0, State *next1, int output1){
this->next0 = next0;
this->output0 = output0;
this->next1 = next1;
this->output1 = output1;
}
// 入力操作を表す関数
// 入力（input）に従って遷移先と出力を返す
void Input(int input, State **next, int *output){
if(input == 0){
*next = next0;
*output = output0;
}else{
*next = next1;
*output = output1;
}
}
};
main()
{
State s0;
State s1;
State s2;
State s3;
s0.SetState(&s0, 0, &s1, 0);
s1.SetState(&s1, 0, &s2, 0);
s2.SetState(&s3, 0, &s2, 0);
s3.SetState(&s0, 1, &s1, 1);
State *cur = &s0;
int output;
int inputlist[14] = {1,1,0,0,1,1,0,1,1,0,0,1,1,0};
for(int i = 0; i < 14; i++){
cur->Input(inputlist[i], &cur, &output);
cout << output;
}
cout << endl;
return 0;
}
