演習問題 : 状態数の最小化
1.異なる出力を生成する状態対を分割
• 2種類の方法で状態の最小化を求めよ
Q+
Q
I =1
I =0
I =1
q0
q5
q0
q5
q7
q2
q7
q6
q1
q6
q3
q4
q1
q1
q3
q3
0
1
0
1
1
0
1
0
0
1
0
1
0
1
0
1
q0
q1
q2
q3
q4
q5
q6
q7
Q+
Q
Π(2)
I =0
I =1
I =0
I =1
r1
r2
r3
3.グループごとに1つの状態に併合
R+
I =1
I =0
I =1
R
r0
Q
Q+
I =0
R+
I =1
I =0
O
I =1
I =0
I =1
r0
r1
r1
r2
r2
r3
r3
r4
r4
状態数最小化の手順
併合表による最小化
Q
I =0
R+
r0
2.遷移先グループが異なる状態対を分割
グループ
Q
Π(1)
O
I =0
Q+
グループ
Q+
O
I =0
I =1
I =0
I =1
q0
q0
q1
0
0
q1
q5
q6
1
1
q2
q0
q3
0
0
q3
q5
q4
1
1
q4
q7
q1
1
0
q5
q2
q1
0
1
q6
q7
q3
1
0
q7
q6
q3
0
1
•
q1,I =0 q2,I =0
q1,I =1 q2,I =1
q0
q1
q2
手法1 状態遷移表の分割
1. 異なる出力を生成する状態対をグループに分割
2. 以下を分割できなくなるまで繰り返す
– 同一の入力に対し、遷移先の状態が異なるグループに
属すればその状態対をグループに分割
等価状態は
( , )( , )( , )
3. グループごとに1つの状態に併合
•
q3
手法2 状態併合表
1. 異なる出力を持つ状態対に×を付ける
2. 遷移先の状態対を記入
3. 以下を×が付かなくなくなるまで繰り返す
q4
q5
q6
– 遷移先に×が付いていればその状態対に×を付ける
4. 等価な状態対を決定
1
演習問題 : 状態数の最小化
• 不完全指定状態遷移表を最小化せよ
Q+
Q
q0
q1
q2
q3
q4
q5
I =0
q5
q1
q1
q2
q3
-
Q
O
I =1
q0
q2
q0
q5
q2
I =0
1
0
1
1
-
両立状態の決定
I =1
1
1
0
0
1
両立状態は
( , )( , )
( , )( , )
( , )( , )
O
I =0
I =1
I =0
I =1
q0
q5
-
1
-
q1
q1
q0
0
1
q2
q1
q2
-
1
q3
q2
q0
1
0
q4
q3
q5
1
0
q5
-
q2
-
1
両立集合の決定
q0
q1
q2
q3
q4
閉包性を満たすかチェック(1)
{ , } { , } { , } { , } { , } { , }
{ , , }
Q+
{ , , }
両立集合は
{0}{1}{2}{3}{4}{5}
{ , }{ , }{ , }{ , }{ , }{ , }
{ , , }{ , , }
{1}{3}{4}{0,2,5}を選んだ場合
R
Q
r0
r1
r2
q1
q3
q4
q0
q2
q5
r3
Q+
I =0 I =1
q1
q0
q2
q0
q3
q5
q5
q1
q2
q2
R+
I =0
O
I =1
I =0
0
1
1
1
-
I =1
1
0
0
1
1
この組み合わせは閉包性を( 満たす ･ 満たさない )
閉包性を満たすかチェック(2)
閉包性を満たすかチェック(3)
{4}{0,3}{1,2,5}を選んだ場合
R
Q
r0
q4
q0
q3
q1
q2
q5
r1
r2
Q+
I =0 I =1
q3
q5
q5
q2
q0
q1
q0
q1
q2
q2
{1}{4}{0,3}{2,5}を選んだ場合
R+
I =0
O
I =1
I =0
1
1
1
0
-
I =1
0
0
1
1
1
この組み合わせは閉包性を( 満たす ･ 満たさない )
R
Q
r0
r1
q1
q4
q0
q3
q2
q5
r2
r3
Q+
I =0 I =1
q1
q0
q3
q5
q5
q2
q0
q1
q2
q2
R+
I =0
O
I =1
I =0
0
1
1
1
-
I =1
1
0
0
1
1
この組み合わせは閉包性を( 満たす ･ 満たさない )
2
問題 : 状態数の最小化
1.異なる出力を生成する状態対を分割
Q+
R+
Q
Π(1)
I =0
I =1
I =0
I =1
• 2種類の方法で状態の最小化を求めよ
Q+
Q
q0
q1
q2
q3
q4
q5
q6
グループ
O
I =0
I =1
I =0
I =1
q0
q0
q3
q0
q1
q3
q1
q3
q5
q4
q6
q5
q6
q2
0
1
0
1
0
0
0
0
1
0
0
0
0
0
r0
r1
r2
2.遷移先グループが異なる状態対を分割
Q+
R+
Q
(2)
Π
I =0
I =1
I =0
I =1
3.グループごとに1つの状態に併合
グループ
r0
R
Q
Q+
I =0
R+
I =1
I =0
O
I =1
I =0
I =1
r0
r1
r1
r2
r2
r3
r3
r4
r4
併合表による最小化
Q
q0
q1
q2
q3
q4
q5
q6
Q+
q0,I =0 q1,I =0
q0,I =1 q1,I =1
O
I =0
I =1
I =0
I =1
q0
q0
q3
q0
q1
q3
q1
q3
q5
q4
q6
q5
q6
q2
0
1
0
1
0
0
0
0
1
0
0
0
0
0
q0
q1
第13回課題(7月21日〆切)
等価状態は
( , )( , )
q2
q3
q4
•
•
•
•
提出日 月 日
学年 2年 ・ 3年 ・ 4年
学籍番号
氏名
q5
3
問題 : 状態数の最小化
両立状態の決定
• 不完全指定状態遷移表を最小化せよ
Q+
Q
q0
q1
q2
q3
q4
q5
I =0
q5
q3
q0
q5
Q
O
I =1
q5
q2
q5
q0
q1
I =0
0
0
0
0
I =1
1
0
0
1
1
I =1
I =0
I =1
q0
q5
-
0
-
q1
-
q5
-
1
q2
q3
q2
0
0
q3
q0
q5
0
0
q4
-
q0
-
1
q5
q5
q1
0
1
{ , , }
{ , , }
R
Q
r1
q2
q0
q3
q1
q4
q5
r3
閉包性を満たすかチェック(2)
r1
r2
q2
q3
q0
q1
q4
q5
r3
q3
q4
Q+
I =0
R+
I =1
I =0
O
I =1
I =0
I =1
閉包性を満たすかチェック(3)
{2}{0,3}{0,1,4,5}を選んだ場合
Q+
I =0
q2
この組み合わせは閉包性を( 満たす ･ 満たさない )
{2}{3}{0,1,4,5}を選んだ場合
Q
q1
{2}{0,3}{1,4,5}を選んだ場合
r2
{ , , , }
両立集合は
{0}{1}{2}{3}{4}{5}
{ , }{ , }{ , }{ , }{ , }{ , }{ , }
{ , , }{ , , }{ , , }{ , , }
{ , , , }
R
q0
両立状態は
( , )( , )
( , )( , )
( , )( , )
( , )
閉包性を満たすかチェック(1)
{ , }{ , }{ , }{ , }{ , }{ , }{ , }
{ , , }
O
I =0
両立集合の決定
{ , , }
Q+
R+
I =1
I =0
O
I =1
I =0
R
Q
r1
q2
q0
q3
q0
q1
q4
q5
I =1
r2
r3
この組み合わせは閉包性を( 満たす ･ 満たさない )
Q+
I =0
R+
I =1
I =0
O
I =1
I =0
I =1
この組み合わせは閉包性を( 満たす ･ 満たさない )
4