Алгоритм 3.2. СА эквивалентті күйінің бірігуі

Кіру КА M^′′ = (Q^′, T, F^′, H, Z^′) жетіспеушіліксіз қалыпта

Шығу: Минимальды СА М" = (Q′, T, F′, H, Z′).

Қадам 1. Бірінші қадамда нөлдік R(0) бөлінуін құрамыз, эквивалентті екі класстан тұратын: СА - Z қорытынды қалпы және Q-Z қорытынды емес қалпы..

Қадам 2. Өткен қадамда R(n) бөлінуін эквивалентті класста бұрынғы күйіне қосылады, олар біркелкі кіру символымен n-1 эквивалентті қалыпқа өтеді

R(n) = {_ri(n): {qij cQ:VtcTF(q_ij,t) ⊆ гДи-1)} Vi, j∈N}.

Қадам 3. Әзірше R(n) ≠ R(n-1 орындалғанша n:=n+1 деп ойлап, қадам 2 – ге өтеміз.

Қадам 4. Қалған бөлінбеген топтардың күйімен және автоматтың жаңа кестесіне енгіземіз.

Қадам 5. СА M эквивалентін анықтап, жаңа енгізулер енгіземіз.

Бөлінбеген топтардың қалпын белгілейміз: X={B,C},Y={D,E}.

M минималды автоматтын аламыз, мұндағы Q^′′={A,X, Y}, Z^′={Y}.

Функцияның M^′′ автоматына өтуі кесте 3.3. көрсетілген

Сурет 3.3 – СА M^′′ минималды өтуі

1) СА шығуын және экран бетінде қорытындысының графы болуы керек;

2) СА жетіспеген қалпын шығару;

3) СА эквивалентті қалпын шығару;

4) Минималды СА графын экран бетіне шығару.

5) Алгоритмге арналған тестер бақылау мысалдарының сериясын өңдейміз.