Z_max może być tworzony systematycznie - poczynając od prawej strony tablicy trójkątnej wpisujemy

3	-
2	2,4; 2,3 2,3,4
1	1,4; 1,3 1,3,4
0	0,4; 0,3; 0,2; 0,1 0,1,3; 0,1,4; 0,2,3; 0,2,4;

Mamy dwie pełne rodziny: I: {0,1,3; 0,2,4} II: {0,1,4; 0,2,3}

Są reprezentowane wszystkie stany pierwotne: 0, 1, 2, 3, 4.

K = {Q₁, Q₂, …, Q_k} - rodzina podzbiorów zbioru stanów Q

Dla każdego
oraz

Jeżeli dla każdego q oraz dopuszczalnych x_j
to K nazywa się rodzina zamkniętą lub pokryciem.

Weźmy rodzinę I z przykładu. Rodzina ta nie jest zamknięta bo dla zgodności Q₂ i Q₄ konieczna jest zgodność Q₁ i Q₄ a Q₁ należy do zbioru nr 1, a Q₂ należy do zbioru nr 2.

Dołączmy więc trzeci zbiór stanów zgodnych Q₁Q₄ {1,4}.

Automat ma wtedy postać

Q	0	1	Y
0,1,3	0,1,3	0,2,4	0
0,2,4	1,4	0,2,4	1
1,4	0,1,3	0,2,4	1

Przykład.

Automat

Q\X	x1	x2	x1	x2
	b	f	0	0
	c	a	1	1
	-	d	-	0
	-	e	-	0
	c	-	1	-
	g	-	1	-
	-	h	-	0
	-	-	-	1

Rodzina stanów maksymalnych zgodnych

Z_max = {beh},{cde},{cdf},{deg},{dfg},{ac},{ag},{fh}

Na początku trzeba sprawdzić warunek pełności i wyznaczyć najmniejsze możliwe rodziny pokrywające zbiór stanów Q. Stan b należy tylko do pierwszego zbioru, stan a tylko do szóstego i siódmego zbioru. Najmniejsze podrodziny muszą zawierać zbiór pierwszy i szósty lub siódmy.

Są to więc rodziny:

{beh} {ac} i trzeba dodać do pełności {dfg}

albo

{beh} {ag} i trzeba dodać do pełności {cdf}

Sprawdzamy czy otrzymane rodziny są zamknięte:

Qnowe\x	x1	x2
beh	cc-	a--
ac	b-	fd
dfg	-g-	e-h

Ta rodzina jest zamknięta wzgl. funkcji przejścia, bo

Qnowe\x	x1	x2
beh	cc-	a--
ag	b-	fu
cdf	--g	de-

Ta rodzina nie jest zamknięta, bo

w żadnym ze zbiorów

Sprawdzanie nie jest potrzebne dla 1-elementowych zbiorów stanów ze względu na warunek pokrycia.

Pierwsza własność.

Rodzina
zbiorów stanów niesprzecznych pokrywa zbiór stanów Q jeżeli

Oznacza to, że każdy stan zbioru Q należy przynajmniej do jednego zbioru
.

Druga własność.

Rodzina K jest zamknięta dla każdego x i każdego zbioru
istnieje taki
, że

Oznacza to, że dla każdego zbioru
i dla każdej litery wejściowej x istnieje zbiór
należący do rodziny, którego podzbiorem jest zbiór stanów następnych
.

Rodzina Z_max (maksymalnych zbiorów stanów niesprzecznych) pokrywa zbiór Q i jest rodziną zamkniętą.

Q\X	0	1
	2,0	6,0
	4,1	1,0
	3,-	-,0
	2,1	5,-
	4,0	8,-
	7,1	2,0
	3,1	6,1
	-,-	3,0

Q', Y

7	x
6	23	x
5	38	x	x
4	35	23 56	37 25	x
3	v	x	37	34	23
2	13	x	47 12	x	15	34
1	36	x	x	24 68	x	23	x
	8	7	6	5	4	3	2

1. Wpisujemy „x” w kratki nie odpowiadające parze stanów takich, że dla dowolnego wektora wejściowego x jeżeli
   i
   są określone to są równe. Czyli wyznaczamy stany sprzeczne.

2. Wpisujemy „v” dla dowolnego x para stanów następnych jest identyczna albo jeden ze znaków jest nieokreślony albo para stanów następnych jest taka sama.

3. Wpisujemy pary stanów następnych, jeżeli nie spełniają warunku (2).

7	x
6	23	x
5	38	x	x
4	35	x	x	x
3	v	x	x	34	23
2	13	x	x	x	15	34
1	x	x	x	24 68	x	23	x
	8	7	6	5	4	3	2

Pary niesprzeczne:

warunki 23, 38, 35, 13, 34, 24, 68, 23, 15

pary 68, 58, 48, 28, 35, 15, 34, 24, 23, 13, 38

2348 135

Q\X		0	1
		2,0	6,0
		4,1	1,0
		3,-	-,0
		2,1	5,-
		4,0	8,-
		7,1	2,0
		3,1	6,1
		-,-	3,0
7	x
6	23			x
5	38			x		x
4	35			23 56		37 25	x
3	v			x		37	34	23
2	13			x		47 12	x	15	34
1	36			x		x	24 68	x	23	x
	8			7		6	5	4	3	2

pola oznaczone na szaro są „przekreślone”

Stąd czytamy: 68, 58, 48, 28, 35, 34, 24, 23, 13

oraz 23, 38, 35, 13, 34, 24, 68, 23, 15, 34, 23

Z_max = {135, 2348, 58, 68, 7}

Para 58 nie jest warunkiem zgodności, więc można ją usunąć.

Z₁ = {135, 2348, 68, 7}

Stan 8 można usunąć ze zbioru 2348 bo pary 28, 48 nie są warunkiem zgodności a para 38 jest warunkiem zgodności dla już usuniętej pary 58.

Z₂ = {135, 234, 68, 7}

Stanu 3 nie można usunąć ze zbioru 234 bo 23 jest warunkiem zgodności 68, ale można go usunąć ze zbioru 135.

Z₃ = Z_min = {15, 234, 68, 7}

Q\X	0	1
1	2,0	6,0
2	2,1	1,0
6	7,1	2,0
7	2,1	6,1

Minimalizacja deterministycznego automatu niezupełnego

Input: Deterministyczny automat niezupełny

Output: Rodzina automatów
o minimalnej liczbie stanów
, z których każdy przedstawia automat A.

Krok 1. Wyznaczyć zbiór par stanów niezgodnych N i zbiór par stanów zgodnych Z (z tablicy trójkątnej)

Krok 2. Wyznaczyć N_max - rodzinę maksymalnych zbiorów stanów niezgodnych (przy pomocy grafu - relacja niezgodności jest tylko symetryczna)

Krok 3. Wyznaczyć rodzinę maksymalnych zbiorów stanów zgodnych Z_max (przy pomocy grafu - relacja zgodności jest zwrotna i symetryczna)

Krok 4. Wyznaczyć w rodzinie Z_max nienadmiarowy zbiór rodzin zupełnych o minimalnej liczbie elementów.

Krok 5. Zdefiniować rodzinę
automatów przedstawiających automat A, przyjmując jako zbiory stanów
rodziny zupełne wyznaczone w kroku 4 i spełniające warunki

Rodzina zupełna K podzbiorów stanów Q to taka rodzina, że każdy element tej rodziny jest maksymalnym zbiorem stanów zgodnych. Rodzina K pokrywa zbiór stanów Q i jest zamknięta.

Automat A' przedstawia A jeżeli: K - zupełna K = {Q₁, Q₂, …, Q_k}

Q' = {q₁, q₂, …, q_k}

oraz
oraz

1.

2.
gdzie

---