教科書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」によって開くことが出来ます.