Page 16 - 4625

Твердження: два стани q та q довільного скінченного
1
2
автомата М з n станами нерозрізнені, якщо вони (n-2)-нероз-
різнені.
Доведення: на першому кроці розіб’ємо множину
станів скінченого автомата на дві підмножини: F та Q\F. На
0
цій основі побудуємо відношення ≡ :
0
q ≡ q , якщо обидва стани одночасно належать F або
1
2
Q\F.
Побудуємо відношення ≡ :
k
k
q ≡ q , якщо q ≡ k−1 q та δ(q , а) ≡ k−1 δ(q , а) для
2
1
1
2
1
2
всіх а ∈ Σ.
Очевидно, кожна побудована множина містить не більше
(n-1) елементів. Таким чином, можна отримати не більше (n-2)
0
уточнення відношення ≡ . Відношення ≡ n−2 визначає класи
еквівалентних станів автомата М.
Алгоритм. Побудова мінімального скінченного автома-
та.
П1. Побудувати скінченний автомат без тупикових ста-
нів.
П2. Побудувати скінченний автомат без недосяжних ста-
нів.
П3. Знайти множини еквівалентних станів та побудувати
найменший (мінімальний) автомат.
Ознайомившись з деякими результатами теорії скінче-
них автоматів, спробуємо зрозуміти, які мови (словникові
множини) є скінчено автоматичними.
Твердження: скінченно автоматними є такі множини:
- порожня словникова множина - ;
- словникова множина, що складається з одного -слова –
{};
- множина {a}, a  .
Доведення: в кожному випадку нам доведеться конструк-
тивно побудувати відповідний скінченний автомат:

15