Page 13 - 4625

Рисунок 3
Навіть при поверхневому аналізі діаграми переходів на-
веденого скінченного автомата видно, що вершини q q , та q
5
3, 4
є «зайвими», тобто при їх вилученні новий автомат буде екві-
валентний початковому. З наведеного вище прикладу видно,
що для отриманого детермінованого скінченного автомата
можна запропонувати еквівалентний йому автомат з меншою
кількістю станів, тобто мінімізувати скінченний автомат. Оче-
видно що серед зайвих станів цього автомата є недосяжні та
тупикові стани.
Означення. Стан q скінченного автомата М називається
недосяжним, якщо на діаграмі переходів скінченного автомата
не існує шляху з q в q.
0
Алгоритм. Пошук недосяжних станів. Спочатку потре-
буємо побудувати множину досяжних станів. Якщо Q – мно-
m
жина досяжних станів скінченного автомата М, то Q/Q – мно-
m
жина недосяжних станів. Побудуємо послідовність множини
Q Q , Q … таким чином, що:
2
0 , 1
П0. Q = {q }.
0
0
П1. Q = S  {q | q ∈ δ(q , a), для всіх a ∈ Σ}.
1
0
0
П2. Q = S i−1  {q | q ∈ δ(q , a), q ∈ Q i−1 та для всіх a ∈
j
j
i
Σ}.
………………………
П Q = Q m+1 =……
m .
m
Очевидно, що кількість кроків П0, П1… скінченна, тому
що послідовність Q монотонна (Q  Q  Q  ….) та
1
2
i
0
обмежена зверху - |Q | < = | Q|.
m
12