2003年度春学期 アルゴリズム論 提出受け付け
第３回リポート課題 形式文法とテューリング機械の比較

記号列: 2進数分数を表す文字列
記号例: 1/1 10/100 10011/1001111 等


形式文法(文脈自由文法)による表記:

G = <{S,A}, {0,1,/}, R, S >

Rは以下の集合:
        S → A/A
        A → 1
        A → A0
        A → A1

L = { 1/1, 1/10, 1/11, 10/1, 10/10, 10/11, ... } = 1[01]*/1[01]*



テューリング機械による表記:

M = ( K, Σ, Γ, δ, q0, F )

K = { q0, q1, q2, q3, q4 }, Σ = {0, 1, /}, Γ = { 0, 1, /, B }, F = {q4}
δ(q,a) = 
        q＼a    0               1               /               B(ブランク記号)
        q0      -               (q1,X,R)        -               -
        q1      (q1,X,R)        (q1,X,R)        (q2,Y,R)        -
        q2      -               (q3,Z,R)        -               -
        q3      (q3,Z,R)        (q3,Z,R)        -               (q4,B,R)
        q4      -               -               -               -



参考文献:

石浦 菜岐佐 (関西学院大学 理工学部 情報科学科 教授)
形式言語とオートマトン 配付資料 (2003 年度版)
http://ist.ksc.kwansei.ac.jp/~ishiura/la/note/n7.pdf