練習用に教科書に載っている簡単なオートマトンを作成し,オートマトンを動作してみます.
シミュレータを使って教科書p.139 図6.5にある電子錠の働きをするオートマトンを 作成してみましょう. なお,このオートマトンシミュレータは数字のかわりに「a」から「j」までの 10種類の文字を入力として受け取ります. そこで教科書に出てくる「1,2,3」は「a,b,c」と読みかえます.
オートマトン動作のチェック表の作成
シミュレータを使う前に, 完成したオートマトンの動きをチェックする表を作りましょう. ここでは,何文字か入力した後, 終了状態になっている(解錠する)かどうかだけに注目します. 「abac」が全部入力されて始めて解錠する, 途中で間違えるとやり直しが効かない, 「abac」の後に何か入力しても二度は解錠しない, といった細かな点もチェックしたいので, それらが確認できるような例も含めるようにします. 問題が曖昧な場合もあるので, そのような場合は,この段階ではっきりさせておきましょう.
入力 | 終了状態 |
無し | 否 |
a | 否 |
ab | 否 |
aba | 否 |
abac | 終了 |
abaca | 否 |
aabac | 否 |
abacabac | 否 |
状態遷移の図の作成
作成した表をもとに必要とされる状態を定めるとともに, それらの状態間の関係を考え, p.139 図6.5 のような図を紙に描きましょう.
シミュレータへの入力
- 状態を作るには,ウインド左上に並んでいる中にある赤丸のボタンをクリックした後, 作った状態を置く場所をクリックします.
- 状態が変化する規則を作るには, ウインド左上に並んでいる中にある線分のボタンをクリックした後, 「元の状態」から「次の状態」までドラッグします. すると,状態間に青色の矢印が引かれ「none」と表示されます. 「none」と書かれた所を右ボタンでクリックすると, 「a, b, ..., j, else, delete」というメニューが出るので,入力文字を選びます. 「else」は,「他の文字全て」を意味します.
- 終了状態を選ぶには,状態を右ボタンクリックして「Final State」を選びます.
- 「A」と書かれたボタンを選ぶと,画面上に文字を書くことができます.
- 状態や状態間の矢印を消すには, それぞれを右ボタンクリックして「delete」を選びます.
- できあがりは下図のようになります.
オートマトンの動作確認
チェック表をもとに作成したオートマトンのテストをしましょう.
- 緑色の三角ボタンをクリックすると,オートマトンの実行がはじまります. 開始状態が緑色になり,画面下の左端の桝目に緑色の三角が現われます.
- キーボードから「a」「b」「a」「c」と順にタイプすると, 下図のように二重丸の終了状態が緑色になり,「解錠」できたことが分かります.
- 緑色の三角ボタンを再度クリックすると オートマトンの状態を元に戻すことができるので, チェック表の他の入力についてもテストします. 「否」と予想した入力をタイプした後, 二重丸の終了状態が緑色になっていないことを確認しましょう. たとえば,下は「aabac」と入力した後の状態です. 緑になっている状態が二重丸でないので, 「否」という予想通りになっていることが分かります.
オートマトンの保存と印刷
作成したオートマトンは「File」メニューの「Save」で, 適当なファイル名を付けて保存できます. また,メニューの「Print」によって印刷することもできます.