Минимальная форма конечного автомата.

М : Х, Z, S, f_Z , f_S

P` = {Σ₁, Σ₂ , …, Σ_r }

Минимальной формой автомата М называют автомат М`, у которого входной алфавит Х, выходной алфавит Z, характеристические функции f<sub>Z</sub> и f<sub>S</sub> совпадают и множество промежуточных состояний S`.

М` : Х, Z, S`, f_Z , f_S

S` = {₁, ₂, …, _r }

Σ_i ↔ _i

Свойства:

1⁰ Минимальная форма автомата единственна с точностью до обозначения.

2⁰ Никакая пара состояний _i и _j не эквивалентны друг другу _i ≠ _j.

3⁰ Минимальная форма автомата содержит наименьшее число состояний среди автоматов, эквивалентных данному.

Доказательство 1⁰:

P_k → P` → M`

Доказательство 2⁰:

От обратного: _i = _j  Σ_i = Σ_j, что противоречит определению k-эквивалентного разбиения автомата.

Доказательство 3⁰:

От обратного: М` = M<sub>1</sub>` = M₂`. Пусть для M<sub>2</sub>` | S₂` | < | S` |. То в нем ₂` → <sub>i</sub>` и ₂` → <sub>j</sub>`, тогда  что _i` = <sub>j</sub>` , что противоречит свойству 2⁰.

Вернемся к задаче 4:

P = {{11}, {12}, {1, 8}, {3, 5}, {2, 4, 6, 10}, {7, 9}}

P = { ₁ = {11}, ₂ = {12}, ₃ = {1, 8}, ₄ = {3, 5}, ₅ = {2, 4, 6, 10}, ₇ = {7, 9}}

P` = {₁, ₂, ₃, ₄, ₅, ₆}

Канонической формой представления автомата считают минимальную форму.

Задача 5:

Монету бросают три раза, если комбинации { Ц Г Г } или { Г Г Г }, начисляется бал.

Х = {Г – герб, Ц – цифра}

Z = { 0, 1}

S = { ЦЦ, ЦГ, ГЦ, ГГ}

S\X	Z v		S v + 1
	Г	Ц	Г	Ц
ЦЦ	0	0	ЦГ	ЦЦ
ЦГ	1	0	ГГ	ГЦ
ГЦ	0	0	ЦГ	ЦЦ
ГГ	1	0	ГГ	ГЦ

P = { Г = { ЦГ, ГГ }, Ц = { ЦЦ, ГЦ }}

S\X	Z v			S v + 1
	Г	Ц	Г		Ц
Ц	0	0	Г		Ц
Г	1	0	Г		Ц

Задача 6:

Построить эвивалентное разбиение автомата. Построить минимальную форму автомата.

S\X	Z v			S v + 1
						
0	0	1	0	0	3	5
1	1	0	1	3	4	7
2	1	0	1	3	0	5
3	0	1	0	3	0	5
4	1	0	1	0	1	7
5	1	0	1	0	5	7
6	0	1	0	3	0	7
7	1	0	1	5	6	8
8	0	0	1	4	3	6
9	1	1	1	5	9	7
10	0	0	1	5	0	6

P1 = {{9}, {8, 10}, {0, 3, 6}, {1, 2, 4, 5, 7}}	1				P2 = {{2}, {7}, {9}, {8, 10}, {0, 3, 6}, {1, 4, 5}}	2				P3 = {{2}, {6}, {7}, {9}, {0, 3}, {8, 10}, {1, 4, 5}}
	0, 3	0, 3	3, 0	5, 5		0, 3	0, 3	3, 0	5, 5
	0, 6	0, 3	3, 0	5, 7		0, 6	0, 3	3, 0	5, 7
	3, 6	3, 3	0, 0	5, 7		3, 6	3, 3	0, 0	5, 7
	1, 2	3, 3	4, 0	7, 5		1, 2	3, 3	4, 0	7, 5
	1, 4	3, 0	4, 1	7, 7		1, 4	3, 0	4, 1	7, 7
	1, 5	3, 0	4, 5	7, 7		1, 5	3, 0	4, 5	7, 7
	1, 7	3, 5	4, 6	7, 8		1, 7	3, 5	4, 6	7, 8
	2, 4	3, 0	0, 1	5, 7		2, 4	3, 0	0, 1	5, 7
	2, 5	3, 0	0, 5	5, 7		2, 5	3, 0	0, 5	5, 7
	2, 7	3, 5	0, 6	5, 8		2, 7	3, 5	0, 6	5, 8
	4, 5	0, 0	1, 5	7, 7		4, 5	0, 0	1, 5	7, 7
	4, 7	0, 5	1, 6	7, 8		4, 7	0, 5	1, 6	7, 8
	5, 7	0, 5	5, 6	7, 8		5, 7	0, 5	5, 6	7, 8
	8, 10	4, 5	3, 0	6, 6		8, 10	4, 5	3, 0	6, 6

P₃ = P₄ = P` = { ₀ = {2}, ₁ = {6}, ₂ = {7}, ₃ = {9}, ₄ = {0, 3}, ₅ = {8, 10}, ₆ = {1, 4, 5}}

S\X	Z v			S v + 1
						
0	1	0	1	4	4	6
1	0	1	0	4	4	2
2	1	0	1	6	1	5
3	1	1	1	6	3	2
4	0	1	0	4	4	6
5	0	0	1	6	4	1
6	1	0	1	4	6	2