Алгоритм мінімізації

Нехай автомат S = {Q, X, Y, d, l, q1} піддається мінімізації. Цей процес складається з:

1. Знаходиться послідовне розбиття p₁, p₂,…, p_k, p_k+1 множини Q на класи одно -, двох -, …, k -, k+1 еквівалентних станів, до тих пір, поки на якомусь k+1 кроці не виявиться, що p_k+1 = p_k. Неважко показати, що тоді розбиття /k = /, тобто що k - еквівалентні стани є в цьому випадку еквівалентними і число кроків k, при якому pk = p не перевищує М- 1, де М - число елементів в множині Q.

2. У кожному класі еквівалентності розбиття p вибираються по одному елементу, які утворюють множину Q' станів мінімального автомата S' = {Q ', X, Y, d, l, q' 1}, еквівалентного автомату S.

3. Функції переходів d' і l' автомата S' визначаються на множині Q' x X. Для цього в таблиці переходів і виходів викреслюються стовпці, відповідні тим що не увійшли до множини Q' станів, а в стовпцях таблиці переходів, що залишилися, усі стани замінюються на еквівалентні з множини Q'.

4. У якості q' 1 вибирається один із станів, що еквівалентний стану q1. Наприклад, зручно за q' 1 приймати само q1.