オートマトンと形式言語

オートマトンと形式言語についての質問です
わかりやすくやり方教えていただけないでしょうか
以下のチューリング機械にaabbを与えたときの様相の途中経過を右下に示す．その時点で読んでいる文字には下線を入れ，また太文字で示している．様相の途中の空欄を適切に埋めなさい．
M=<Q, Γ, Σ, δ, q0, B, F>，
ここで
Q = {q0, q1, q2, q3, qf}
Γ = Σ∪ A, B ∪{¢, $, N}
Σ = {a, b}
q0 = q0
B =B
F = qf

δ: Q✕Γの部分集合→ Q✕Γ✕{L, R}
δ(q0, a)=(q1, A, R), δ(q0, B)=(q3, B, R),
δ(q1, a)=(q1, a, R), δ(q1, b)=(q2, B, L),
δ(q1, B)=(q1, B, R), δ(q2, a)=(q2, a, L),
δ(q2, A)=(q0, A, R), δ(q2, B)=(q2, B, L),
δ(q3, B)=(q3, B, R), δ(q3, $)=(qf, $, L)

(q0,aabb)⊢( □,□□□□)
⊢*( q1 , A A B b )
⊢( □,□□□□)
⊢*( q2 , A A B B )
⊢( □,□□□□)
⊢( □,□□□□)
⊢( qf,□□□□)

質問者からの補足コメント

• 

  一番上の空欄はδ(q0, a)=(q1, A, R)で(q1,Aa*bb)になるのはわかりましたが,
  次はδ(q1,a)=(q1,a,R)にしたがって,(q,Aab*b)
  次にδ(q1,B)=(q1,B,R)にしたがって、Bがないのですがどうすればいいのでしょうか

  No.1の回答に寄せられた補足コメントです。 補足日時：2015/07/31 00:08

• 

  理解できました
  ありがとうございました

  No.2の回答に寄せられた補足コメントです。 補足日時：2015/07/31 13:51

No.2 ベストアンサー 回答者： stomachman 回答日時： 2015/07/31 08:51

機械の動作を自分でやってみせろ、というだけの話ですから、もちろん、正確に動作しなくちゃいけない。

> δ(q1,a)=(q1,a,R)にしたがって,(q,Aab*b)

違います。不注意だな。

> 次にδ(q1,B)=(q1,B,R)にしたがって

読んでる文字はBではないのに、なんでそれに従おうとするんですかね？？

この回答へのお礼

わかりました。ありがとうございました

お礼日時：2015/08/01 12:20

No.1 回答者： stomachman 回答日時： 2015/07/29 05:08

記号の説明がないので、質問が成立していません。

意味も分からず丸投げするカワイソウな人なんだなーってことがよく伝わります。

　ま、推測しますと、

　Qが状態の集合。
　q0=q0ってのは全くのナンセンスですけど、状態q0から出発ってことでしょ。F=qfもおかしな話で、F={qf}なら意味がある。終状態の集合がFってことですよ、きっと。
　Σは入力に使われるアルファベットだと思われ、Γは出力に使われるアルファベットかなと思うと、いやΓ = Σ∪ A, B ∪{¢, $, N}はまるで意味不明で、Γ = Σ∪ {A, B} ∪{¢, $, N}じゃないのかな。"{¢, $, N}"という３つの要素については、どうも特別な意味を持つ文字のようですが、なんじゃこりゃ。
　δが状態遷移を表しているんでしょ。$を出力する所がδ(q3,$)だけであるところを見ると、どうやら$は「入力文字列の終わり」を表す記号であって、入力に最初からくっついていると考えるようです。間抜けな記法であって気に入らんので、以下ではこれを陽に書く事にしましょうかね。
　"R", "L"はヘッドをそれぞれ右・左に動かすってことを表しているんでしょう。さもないとチューリングマシンぽくなりませんから。下線の代わりに文字の右肩に*を付けましょう。

q0に"a*abb"を突っ込んだらどうなるか。終わりの記号を含めると"a*abb$"ですかね。つまり(q0,a*abb$)
状態はq0、読んでる文字は"a"ですから、δ(q0,a)=(q1,A,R)に従って、状態はq1になり、"a"を"A"に書き換えて、右に行く。(q1, Aa*bb$)
状態はq1、読んでる文字は"a"ですから、δ(q1,a)=(q1,a,R)に従って、状態はq1になり、"a"を"a"に書き換えて、右に行く。(q1,Aab*b$)
：（途中省略）
状態はq3、読んでる文字は"$"ですから、δ(q3,$)=(qf,$,L)に従って、状態はqfになり、"$"を"$"に書き換えて、左に行く。(qf,AABB*$)
qf∈Fなんで、これでおしまい。

というわけで、停止するようです。省略部分は自分でやりなされ。