計算言語２（スタック付きオートマトン）
このページはマス旅の一部です。
前回、計算式が受理できるかどうかを判定する有限オートマトン(DFA)を作りました。
今回は、スタックを使って答えの出せるオートマトンを作ろう。
スタックつきオートマトンのことを「プッシュダウン・オートマトン(PDA」と呼ぶ。
スタックに積むことをプッシュといい、
スタックの先頭（最上位）を取り出すことをポップといった。
計算式は前回同様で「a+b」を「ab+」と、後置式でかきましょう。
＜スタックの使い方＞
Σ={0,1,+,x}について、N,M∊[0,1],C,D∊[+,x]とラベルを貼ろう。
1演算記号式"NMC"の計算は
①Nを読んで、Nをスタックに積む。スタック先頭がN。
②Mを読んで、Mをスタックに積む。スタック先頭がM。
➂Cを読んで、MをポップするとNがスタックに残る。
このあと3種類に分岐する。
もし、C="x"でM=1か、C="+"でM=0なら、何もスタックに積まない。スタック先頭はN。
もし、C="x"でM=0ならば、スタックに0を積む。スタックには0Nが積んである。スタック先頭は0。
最後の場合、C="+"でM=1なら何も積まず、NをポップしてNを反転してスタックに積む。Nの反転がスタック先頭。
（つまり、0+1=1, 1+0=0という計算をしている。）
④最後のステップは、ポップするとスタック先頭Pを答えにできる。
2演算記号式"NMCLD"の計算はどうなるだろうか。
"NMC"まで済んでいるとしたら、
NMCの最後のステップ④をやらずに、
NMCの最初のステップ①も不要になる。Nの代わりにPとなる。スタック先頭がPになっている。
あとは、②のMのかわりにLを読んで、Lをスタックに積む。スタック先頭がLになる。
➂はD読んでLをポップする。スタック先頭がPになる。。。。省略。スタック先頭はPか０か反転Pになる。
④最後のステップは、ポップするとスタック先頭にあった数を答えにできる。
こんな流れになるね。
＜推移関数を作ろう＞
以上をまとめて状態推移関数を作ろう
状態Q={q1,q2,q3,q4,q5}
q1="",q2=N,q3=NM,q4=+1,q5="err"
スタック格納文字Γ={0,1}
エラーにならない対応表だけ抜き出してみよう。
δ関数3要素⇒2要素のしくみになる。
（現在状態、入力記号、スタック「先頭」）＝>(次の状態、プッシュする記号列）
プッシュする文字がないときは「ε」を使います。
状態q3、q4での動きが複雑ですが、鍵になりますよ。
状態q1は入力記号をプッシュするから、
(q1 , 0 ,Λ) ⇒(q2 , 0)
(q1 , 1 ,Λ) ⇒(q2 , 1)
状態q2も入力記号をプッシュするが、空Λはプッシュできないので判定して終わりだから、
(q2 , 0 ,0 ) ⇒(q3 , 00)
(q2 , 0 ,1 ) ⇒(q3 , 01)
(q2 , 1 ,0 ) ⇒(q3 , 10)
(q2 , 1 ,1 ) ⇒(q3 , 11)
(q2 , Λ,N ) ⇒受理される。
状態q3は、入力演算記号とスタック先頭の組み合わせで4通りに分岐して、
(q3 , + ,0 ) ⇒(q2 , ε) ＋算は、ポップが０なら残りをそのまま。
(q3 , + ,1 ) ⇒(q4 , ε) ＋算は、ポップが１なら残りをそのままでq4へ
(q3 , x ,0 ) ⇒(q2 , 0) ×算は、ポップが０なら０をプッシュ。
(q3 , x ,1 ) ⇒(q2 , ε) ×算は、ポップが１なら残りをそのまま。
状態q4は、q3⇒q2の流れのサブ状態のようなものです。記号残りをポップ(0/1)し、反転(1/0)してプッシュするが読み取り位置は足踏みする。(q3 , + ,1 ) ⇒(q4 , ε)からの足踏みなので、q4でも入力記号は＋です。
(q4 , ＋ ,1 ) ⇒(q2 , 0)
(q4 , ＋ ,0 ) ⇒(q2 , 1)
それ以外の組み合わせはすべてエラー。
(q1,_._),(q2,_,_),(q3,_,_).(q4,_._),(q5,_,_) ⇒q5
課題：以上のM＝（Q,Σ、Γ、δ、q1,F)で、F={q2}すると、"01+1x"が受理され答えが１となることを確かめよう。
＜手動デバック＞
[q, s, γ]はマシンMが状態qで記号列s、スタックがγのときのプロセスを書き出そう。
[q1,"0 1 + 1 x",Λ]更新 (q1,0,Λ)=>(q2,0) プッシュ0
[q2,"1 + 1 x" ,0 ]更新 (q2,1,0 )=>(q3,10) プッシュ1
[q3,"+ 1 x" ,10]更新 (q3,+,1)=> (q4,0) ポップ１
[q4,"1 x" , 0]更新 (q4,1,0)=> (q2,1) ポップ０、スタック０を反転してプッシュ１
[q2,"1 x" , 1]更新 (q2,1,1)=> (q3,11) q4と同じ記号状態を入力記号列とする。入力記号１をそのままプッシュ１
[q3,"x" ,11]更新 (q3,x,1)=> (q2,1) ポップが１だから、1が残る。
[q2,Λ, , 1]更新 (q2,Λ,1)=> 受理「１」が答え
PDA(プッシュダウン・オートマトン）
＜geogebraでコード化＞
#プログラムのデザインパターンは前回同様、「作成」で基本設定し、「リセット」で初期化、
「更新」でwhileのように順次プロセスを進めるというものです。
#スタック用の変数がstackStrです。
#更新を押すと、
新状態nextStateを現状態curQにセットします。
状態がq4のときは、読み取り位置posを足踏みしますが、それ以外ではposは１つ進み入力文字列InputStrを読みChaInにセットします。
状態文字qiの数字iの部分を状態位置変数diにセットします。
スタック最上位topSは、スタックstackStrが空ならΛとし、それ以外ではstackStrの先頭1文字を読みます。
残り文字restStrはposがInputStrの長さを超えたらΛを、越えなければ、posから最後までセット。
（状態位置変数di、読み取り文字charIn、スタック先頭topS）の組み合わせに応じて、
次の状態文字をcalcNextで求めます、これはIfをネストさせることで長文コマンドで乗り切りましょう。
nextStateをcalcNextで上書きしましょう。ここまでで、状態表示変数が出そろので、
Processに、
読み取り位置pos :＜現状態curQ , 残り文字列reststr , スタックstackStr＞ ==> 次の状態 ( 読み取り文字)
と表示されるようにします。
次は、stackStrも更新しておきましょう。
スタックの2文字をsubstackに格納します。
状態番号diが1なら読み取り文字charIn
状態番号diが2なら,空でなければ、読み取り文字charInをスタックに載せます。
状態番号diが3なら,読み取り文字charInが＋ならsubstackのまま、charInがｘのときはスタック先頭topSが0なら0をsubstackにのせ、1ならsubstackのまま。
状態番号diが4ならtopSが0ならスタックに１をのせ、1ならスタックに０をのせます。
最後に、入力文字が空で現状態curQがq2のときは受理します。
「作成」ボタン
#必要な変数を用意します。クリック時のスクリプトに貼り付けてください。
pos = 0
InputStr = "01+1x"
Len = Length(InputStr)
Input = Join(Split(InputStr, {""}), {"Λ"})
q1 = "q1"
q2 = "q2"
q3 = "q3"
q4 = "q4"
q5 = "q5"
curQ = q1
nextState = q1
stackStr = ""
substack= ""
charIn = ""
di = 1
reststr = InputStr
result = ""
Process = pos + ":＜q1, " + reststr + ", Λ＞ ==> q1"
「リセット」ボタン
SetValue(pos, 0)
SetValue(curQ, "q1")
SetValue(nextState, "q1")
SetValue(stackStr, "")
SetValue(substack, "")
SetValue(charIn, "")
SetValue(di, 1)
SetValue(reststr, InputStr)
SetValue(result, "")
SetValue(Process, "0:＜q1, " + InputStr + ", Λ＞ ==> q1")
「更新」ボタン
SetValue(curQ, nextState)
SetValue(pos, If(curQ == "q4", pos, If(pos < Length(Input), pos + 1, pos)))
SetValue(charIn, Element(Input, pos))
di = If(curQ == "q1", 1, If(curQ == "q2", 2, If(curQ == "q3", 3, If(curQ == "q4", 4, 5))))
topS = If(stackStr == "", "Λ", Take(stackStr, 1, 1))
SetValue(reststr, If(pos > Len, "Λ", Take(InputStr, pos, Len)))
calcNext = If(di == 1, If(charIn == "0" || charIn == "1", "q2", "q5"), If(di == 2, If(charIn == "0" || charIn == "1", "q3", If(charIn == "Λ", "q2", "q5")), If(di == 3, If(charIn == "+" && topS == "1", "q4", If((charIn == "+" && topS == "0") || (charIn == "x" && topS == "1") || (charIn == "x" && topS == "0"), "q2", "q5")), If(di == 4, If(charIn == "+", "q2", "q5"), "q5"))))
SetValue(nextState, calcNext)
SetValue(Process, pos + ":＜" + curQ + ", " + reststr + ", " + If(stackStr == "", "Λ", stackStr) + "＞ ==> " + calcNext + "(" + charIn + ")")
SetValue(substack,If(Length(stackStr) >= 2, Take(stackStr, 2), ""))
SetValue(stackStr, If(di == 1, charIn, If(di == 2 && charIn != "Λ", charIn + stackStr, If(di == 3 && charIn == "+", substack, If(di == 3 && charIn == "x" && topS == "0", "0" + substack, If(di == 3 && charIn == "x" && topS == "1", substack, If(di == 4, If(topS == "0", "1" +substack, "0" + substack ), stackStr)))))))
SetValue(result, If(charIn == "Λ" && curQ == "q2", "受理 (ANSWER = " + stackStr + ")", result))
＜振り返り＞
更新は、SetValueの連発、Ifコマンドのネストしまくりですね。入力は改行を入れませんが、
読むときはIfの前で区切って表示すると、日本語に直して読みやすくなりますよ。