w/計算理論の基礎[原著第2版] - [A]1.1 1.2 1.3 Diff

!1.1!1.1 '''<解答チェック済み>'''

(状態遷移図M1,M2 略)

:a. 開始状態はどれか？:M1:''q1'', M2:''q1''
:b. 受理状態の集合は何か？:M1:''{q2}'', M2:''{q1,q4}''
:c. 入力 aabbに対して，機械が通過する状態の列は何か？:M1:''(q1,q2,q3,q1,q1)'', M2:''(q1,q1,q1,q2,q4)''
:d. 機械は文字列 εを受理するか？:M1:''受理しない'', M2:''受理する''

!1.2!1.2 '''<解答チェック済み>'''

""1.1で示された機械 M1と M2の正式な記述を与えよ．

'''<「正式な」とあれば五個組で書くべき？>'''

!!M1

#Q:{q1,q2,q3}
#Σ:{a,b}
#δ:
#-||||!a||!b||
#-||!q1||q2||q1||
#-||!q2||q3||q3||
#-||!q3||q2||q1||
#q0:q1
#F:{q2}

!!M2
#Q:{q1,q2,q3,q4}
#Σ:{a,b}
#δ:
#-||||!a||!b||
#-||!q1||q1||q2||
#-||!q2||q3||q4||
#-||!q3||q2||q1||
#-||!q4||q3||q4||
#q0:q1
#F:{==q2=='''q1''',q4}

!1.3

""DFA Mの正式な記述は ({q1,q2,q3,q4,q5},{u,d},δ,q3,{q3}) である．ただし， δが以下の表で与えられる．この機械の状態遷移図を与えよ．
""||||!u||!d||
""||!q1||q1||q2||
""||!q2||q1||q3||
""||!q3||q2||q4||
""||!q4||q3||q5||
""||!q5||q4||q5||

{{attach_view'1.3.gif','[A]1.1 1.2 1.3'}}
{{attach_anchor_string'ソースファイル (1.3.dot)','1.3.dot', '[A]1.1 1.2 1.3'}}

俺、図書いてない Σ(ﾟДﾟ;