計算言語１（有限オートマトン）
このページはマス旅の一部です。
今回は、「有限オートマトン」を探ってみよう。
日本では、昔、
パソコンは、ソフトがなければただの箱
なんてコトバがはやりました。
でも、その逆も真です。
ソフトがあっても「ハード」がないと結果が出ない。
言語があっても「マシン」がないと計算は実現できません。
だから、
計算言語にとってもマシンは必要になります。
マシンといっても実物だと、その性能に引っ張られてしまい理論化は混乱しますね。
そこで、「計算マシンのモデル」として作られたのが「有限オートマトン」です。
正確にいうと「計算できるかの判定をするマシンのモデル」が有限オートマトンです。
まあ、記号列をデバッグするソフトというとわかりやすいですね。
日々の仕事や学習に追われていると、
その内部、その動作原理、その歴史はどうなっているんだろうという問いを
浮かんだとしても、タイパ、コスパを考えて抹消してしまいがちですね。
今回は、単純で抽象的だけど、
高級言語の動作を理論的に裏側で支えている「有限オートマトン」で遊ぼう。
くわしくはこちら、「正規表現2（状態遷移図とオートマトンで遊ぶ）」（https://www.geogebra.org/m/ddm5798j#material/mtukwqzu）
有限オートマトンによって、状態を遷移して、受理状態というゴールに届けば
デバッグ成功だ。状態遷移を確率とともに図で表したものが状態遷移図だったね。
くわしくはこちら、「情報発生をモデル化しよう」
（https://www.geogebra.org/m/ddm5798j#material/q6sj8zvg）
遷移関数が決まっているオートマトン（DFA）に取り組もう。
i j + k xを受理し、それ以外を却下するマシンMを作ります。
課題：次のM＝（Q,Σ、δ、q1,F)は記号"0 1 + 1 x"を受理するか。
Q={q1,q2,q3,q4,q5,q6,q7,q8},Σ={0,1,+,x},F={q2,q3}
各状態qnは記号を読み取って記憶する状態で、次のように定める。
{q2,q3,q4,q5,q6,q7}⇒{0,1,0 0,0 1,1 0,1 1}
遷移関数qn(*)の*=0,1,+,xに対する返り値は以下のテーブルδで決まる。
δ表===========
現状態| 0 1 + x
q1初期:q2,q3,q8,q8
q2 0 :q4,q5,q8,q8
q3 1 :q6,q7,q8,q8
q4 0 0 :q8,q8,q2,q2
q5 0 1 :q8,q8,q3,q2
q6 1 0 :q8,q8,q3,q2
q7 1 1 :q8,q8,q2,q3
q8エラー:q8,q8,q8,q8
==============
F={q2,q3}だから、q2かq3で受理となる。
q8はエラーの表示。
＜手作業デバッグ＞
[q, s]はマシンMが状態qで記号列sを処理していることを表すとしましょう。
[q1,"0 1 + 1 x"]==> q1(0)= q2
[q2,"1 + 1 x" ]==> q2(1)= q5
[q5,"+ 1 x" ]==> q5(+)= q3
[q3,"1 x" ]==> q3(1)= q7
[q7,"x" ]==> q7(x)= q3
[q3,Λ] ==>受理
有限オートマトンを作ろう
＜geogebraコード＞
geogebraのIf文はswitch式で辞書のような書き方ができます。
状態を1文字入った変数リストとして設定してから、関数として上書きします。
文字列をカンマ区切りとしましょう。
#「作成」ボタン
# resultが受理かどうかの結果を表示する文字列なので、サイズ大で緑にします。
# InputStrを入力コントロールのオブジェクトに指定し、「入力文字列」とします。
# 入力文字列の最後に"Λ"をつけることで、読み取りが空になったときの判断ができます。
# Processが手作業デバッグと同様な表示ができるので、サイズ大で太字、青にしましょう。
pos = 0
InputStr = "01+1x"
Len = Length(InputStr)
Input = Join(Split(InputStr, {""}), {"Λ"})
q1 = {""}
q2 = {"0"}
q3 = {"1"}
q4 = {"00"}
q5 = {"01"}
q6 = {"10"}
q7 = {"11"}
q8 = {"err"}
curQ = q1
Q = {q1, q2, q3, q4, q5, q6, q7, q8}
F = {q2, q3}
sig = {"0", "1", "+", "x"}
Delta = { {q2, q3, q8, q8}, {q4, q5, q8, q8}, {q6, q7, q8, q8}, {q8, q8, q2, q2}, {q8, q8, q3, q2}, {q8, q8, q3, q2}, {q8, q8, q2, q3}, {q8, q8, q8, q8} }
result = ""
nextState = q1
charIn = ""
di = 1
dj = 0
reststr = InputStr
Process = pos + ":＜q" + di + ", " + reststr + "＞ ==> q" + di + "(" + charIn + ")=" + Element(nextState, 1)
「リセット」ボタン
SetValue(pos, 0)
SetValue(curQ, q1)
SetValue(result, "")
SetValue(nextState, q1)
SetValue(charIn, "")
SetValue(di, 1)
SetValue(dj, 0)
「更新」ボタン
SetValue(curQ, nextState)
SetValue(pos, If(pos < Length(Input), pos + 1, pos))
SetValue(charIn, Element(Input, pos))
dj = If(charIn == "0", 1, charIn == "1", 2, charIn == "+", 3, charIn == "x", 4, 0)
qStr = Element(curQ, 1)
di = If(qStr == Element(q1, 1), 1, qStr == Element(q2, 1), 2, qStr == Element(q3, 1), 3, qStr == Element(q4, 1), 4, qStr == Element(q5, 1), 5, qStr == Element(q6, 1), 6, qStr == Element(q7, 1), 7, qStr == Element(q8, 1), 8, 8)
SetValue(nextState, If(charIn == "Λ", curQ, Element(Delta, di, dj)))
SetValue(result, If(pos > Len, If(IndexOf(curQ, F) > 0, "受理 (ACCEPT)", "棄却 (REJECT)"), result))
＜振り返り＞
入力文字を変えることで、受理か棄却の結果が変わります。
たとえば、リセットしてから、文字列を変えて実験してみよう。
0１＋１は5回で棄却されます。
0 1 x 1 + は6回で受理されます。
何が現在の状態で、何が次の状態となるのかを更新で明確な順序でかくことが大切だね。
また、他の言語によくあるwhileの脱出構文を,
geogebraではボタンを押すことで実現できますね。