Page 14 - 4625

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

Рисунок 4

13