Минимальная форма конечного автомата.
М : Х, Z, S, fZ , fS
P` = {Σ1, Σ2 , …, Σr }
Минимальной формой автомата М называют автомат М`, у которого входной алфавит Х, выходной алфавит Z, характеристические функции fZ и fS совпадают и множество промежуточных состояний S`.
М` : Х, Z, S`, fZ , fS
S` = {1, 2, …, r }
Σi ↔ i
Свойства:
10 Минимальная форма автомата единственна с точностью до обозначения.
20 Никакая пара состояний i и j не эквивалентны друг другу i ≠ j.
30 Минимальная форма автомата содержит наименьшее число состояний среди автоматов, эквивалентных данному.
Доказательство 10:
Pk → P` → M`
Доказательство 20:
От обратного: i = j Σi = Σj, что противоречит определению k-эквивалентного разбиения автомата.
Доказательство 30:
От обратного: М` = M1` = M2`. Пусть для M2` | S2` | < | S` |. То в нем 2` → i` и 2` → j`, тогда что i` = j` , что противоречит свойству 20.
Вернемся к задаче 4:
P = {{11}, {12}, {1, 8}, {3, 5}, {2, 4, 6, 10}, {7, 9}}
P = { 1 = {11}, 2 = {12}, 3 = {1, 8}, 4 = {3, 5}, 5 = {2, 4, 6, 10}, 7 = {7, 9}}
P` = {1, 2, 3, 4, 5, 6}
Канонической формой представления автомата считают минимальную форму.
Задача 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 |
P3 = P4 = P` = { 0 = {2}, 1 = {6}, 2 = {7}, 3 = {9}, 4 = {0, 3}, 5 = {8, 10}, 6 = {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 |