1. シミュレータの実行

教科書6.1節の例として挙げられている文字列中に「aba」が現れるか否かを判定するオートマトン(図6.2)をシミュレータプログラム上で実行してみます.なお,以下の説明では始状態を「初期状態(initial)」,受理状態を「終了状態(final)」,受理状態以外の状態(つまり拒否となる状態)を「非終了状態(non-final)」と呼ぶこととします.

オートマトンシミュレータの起動

以下のリンクをクリックし,オートマトンシミュレータを起動してみましょう.

https://tanakat01.github.io/AutoSimJS/

次のようにシミュレータが起動されるはずです.なお,以降,解説中の図はクリックすると拡大します.

シミュレータへの入力

教科書の図6.2のように4つの状態を作りましょう.状態を作るには,ウィンドウ左上に4つ並んでいるボタンの中で赤丸のボタンをクリックした後,状態を配置する場所をクリックします.

状態を終了状態として指定するには,状態の上で右ボタンクリックして「Final State」を選びます.状態の指定を削除したり,初期状態として指定したりすることも可能です(初期状態は必ず1つですから,下の状況では「Initial State」を選択できなくなっています).

状態遷移の規則(矢印)を作るには,ウィンドウ左上に4つ並んでいるボタンの中で線分のボタンをクリックした後,「元の状態」から「次の状態」までドラッグします.すると,状態間に青色の矢印が引かれ「none」と表示されます.「none」と書かれた所を右ボタンでクリックすると,「a, b, ..., j, else, Delete」というメニューが出るので,入力文字を選びます.「else」は「他の文字全て」を意味します.状態や状態遷移の規則を削除するには,それぞれの上で右ボタンをクリックして「Delete」を選択します.すべてを消して最初から始める場合には,「File」メニューの「New -> Deterministic Finite Automaton」を選択するか,ブラウザのリロードボタンを押すと良いでしょう(前者の場合,「Are you sure you want to clear everything for a new project?」と聞いてくるので「OK」を選択します).

以下のように図6.2のオートマトンを作りましょう.複数種類の文字で(下の例では「a」または「b」のどちらでも)遷移するように指定することも可能です.

左上のラベル領域にオートマトンの名称を記入できます(ただし,この名称は保存されないようです).

オートマトンの動作確認

ウィンドウ左上に4つ並んでいるボタンの中で緑色の三角ボタンをクリックすると,オートマトンの実行がはじまります.初期状態が緑色になり,画面下の左端の桝目に緑色の三角が現われます.

キーボードから「a」をタイプすると,画面下の左端の桝目に「a」と表示され,遷移した状態が緑色になります.

続いてキーボードから「b」と「a」をタイプすると,下の図のように二重丸の終了状態が緑色になります.

ウィンドウ左上に4つ並んでいるボタンの中で緑色の三角ボタンをクリックすると,オートマトンを最初から実行することができます.初期状態が緑色になり,画面下の左端の桝目に緑色の三角が現われます.Deleteキー(WindowsではBackSpaceキー)によって入力した文字を1文字ずつ消去することも可能です.以下は「bbaabab」と入力した後の状態です.途中に「aba」が含まれていますので,終了状態が緑色になっています.

オートマトンの保存と印刷

作成したオートマトンは「File」メニューの「Save」で保存したり,「Save Image」で画像として保存したりできます.前者の場合,ダウンロードディレクトリに「machine.txt」という名前で,後者の場合には同じくダウンロードディレクトリに「automaton.png」という名前で保存されます.

保存したオートマトンは,メニューの「Open」によって開くことが出来ます.