29ページ
30ページ
q
0 ⇨ ε⇨ ⇨
q
0q
0 1r q
0 10t
30ページ
30ページ
到達不可能状態s を除去しても等価 M1 M2
30ページ
状態が初期状態から到達可能か不可能かを調べるには 到達可能状態検出木 を作る
30∼31ページ
30∼31ページ
30∼31ページ
31ページ
二つのオートマトンが等価かどうかを判定するには 等価性判定木 を作る
31ページ
二つの初期状態が 等価であると仮定
31ページ
31ページ
31ページ
31ページ
31ページ
q1 , q3 . r1は最終状態なので q1 r1 , q3 r1 としても 矛盾しない
31ページ
最後まで矛盾なく
等価性判定木が作れたので M1 M2
32ページ
r0は最終状態でない s1は最終状態
したがって
r0 s1 は矛盾する
79ページ