[A]1.1 1.2 1.3

(状態遷移図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.1で示された機械 M1と M2の正式な記述を与えよ．

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

M1

1. Q:{q1,q2,q3}
2. Σ:{a,b}

3. δ:

   	a	b
   q1	q2	q1
   q2	q3	q3
   q3	q2	q1

4. q0:q1
5. F:{q2}

M2

1. Q:{q1,q2,q3,q4}
2. Σ:{a,b}

3. δ:

   	a	b
   q1	q1	q2
   q2	q3	q4
   q3	q2	q1
   q4	q3	q4

4. q0:q1
5. F:{q2q1,q4}

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

ソースファイル (1.3.dot)

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