Документ: PZ_14_dlya_studentov, страницы 6-10 | Студенческое хранилище

Для примера рассмотрим еще пару ячеек. Если все понятно, то переходите к следующему шагу.

Смотрим ячейку (4,5). Она содержит пару 2,9. Ячейка (2,9) не является вычеркнутой, следовательно, ничего не делаем и проверяем дальше.

Смотрим ячейку (4,7). Она содержит пары 2,8 и 3,1. Ни ячейка (2,8), ни ячейка (1,3) не зачеркнуты. Ничего не вычеркиваем. Проверяем дальше.

Смотрим ячейку (5,7). Она содержит пары 8,9 и 1,3, следовательно, мы ее не вычеркиваем.

У нас зачеркнута ячейка (2,7), следовательно, вычеркиваем все клетки, в которых содержится пара 2,7 (или 7,2). Это клетки (1,8), (1,9), (3,8), (3,9). Вычеркиваем их.

Пустые клетки мы не проверяем.

Шаг 5. Составляем классы эквивалентности.

Каждой не зачёркнутой клетке соответствует пара эквивалентных состояний, которые мы объединяем в классы эквивалентности.

Смотрим первый столбец, какие ячейки у нас не зачеркнуты: (1,3). Следовательно, первый класс будет:

A= {1,3} (первый столбец)

Смотрим второй столбец, какие ячейки у нас не зачеркнуты: (2,8), (2,9). Следовательно, второй класс эквивалентности будет множество из этих значений (Записываем без повторений, т.к. это множество):

Б= {2,8,9} (второй столбец)

Смотрим четвертый столбец. Ячейки: (4,5), (4,7). Данные значения у нас не было задействованы в предыдущих классах, следовательно, все их включаем:

В= {4,5,7} (четвертый столбец)

Пятый столбец – ячейка (5,7). И 5, и 7 у нас уже включены в класс эквивалентности В., следовательно, пропускаем и переходим к 6 столбцу.

Шестой столбец – все вычеркнуты. Пропускаем.

Седьмой – все вычеркнуты. Число 7 уже было включено. Пропускаем.

Восьмой столбец – ячейка (8,9). И 8, и 9 были выключены в класс Б., следовательно, пропускаем.

Пройдясь по всем столбцам, в которых есть хотя бы одна не зачеркнутая клетка, смотрим, какие состояния у нас не были включены.

Но так как число 6 у нас не было включено в другие классы, то наш класс эквивалентности, следующий будет содержать только число 6.

Г= {6} (шестой столбец)

Если бы у нас не содержалось еще какое-то число в классах, например, 12, то мы бы сделали еще отдельно класс с числом 12.

У нас получилось 4 класса эквивалентности:

A= {1,3}

Б= {2,8,9}

В= {4,5,7}

Г= {6}

Шаг 6. Строим минимальный автомат с 4 состояниями А, Б, В, Г.

Исходная таблица

A/Q	1	2	3	4	5	6	7	8	9
a	2, x	4, x	2, x	2, x	9, x	9, y	8, x	7, x	7, x
b	3, x	6, x	1, x	3, y	3, y	7, y	1, y	6, x	6, x

Для построения таблицы состояний минимального автомата поступаем следующим образом: чтобы найти значении функций перехода и выхода, например на наборе (А,а), выбираем из класса эквивалентности А любого представителя.

A= {1,3}

Пусть это будет состояние 3. Смотрим 3-й столбец исходной таблицы.

A/Q	3
a	2, x
b	1, x

Заполняем столбец А соответствующими буками. (х, х).

Далее разбираема с числами, которые были в исходной таблице (2, х), (1, х) 2 и 1.

2 Б={2,8,9} – 2 принадлежит классу эквивалентности Б.

1 A={1,3} – 1 принадлежит классу эквивалентности А.

Следовательно записываем в Столбец А таблицы минимального автомата пары (Б,х), (А,х).

A/Q	А
a	Б, x
b	А, x

.

Б={2,8,9}

Возьмем для заполнения 9 состояние. Следовательно, смотрим 9-й столбец исходной таблицы.

A/Q	9
a	7, x
b	6, x

7 В={4,5,7},

6 Г={6} .

A/Q	Б
a	В, x
b	Г, x

.

В={4,5,7}

Возьмём 4 состояние (или любое другое).

A/Q	4
a	2, x
b	3, y

2 Б={2,8,9}

3 A={1,3}

A/Q	Б
a	Б, x
b	А, y

.

Г={6}

Тут выбора, какое состояние брать у нас нет, поэтому берем 6.

A/Q	6
a	9, y
b	7, y

9 Б={2,8,9}

7 В={4,5,7}

A/Q	Б
a	Б , y
b	В , y

.

Записываем все столбцы, которые нашли в таблицу.

Получаем минимальный автомат:

	А	Б	В	Г
a	Б , x	В , x	Б , x	Б , y
b	А, x	Г , x	А , y	В , y

IШаг 7. Проверим работу исходного автомата

Исходная таблица

A/Q	1	2	3	4	5	6	7	8	9
a	2, x	4, x	2, x	2, x	9, x	9, y	8, x	7, x	7, x
b	3, x	6, x	1, x	3, y	3, y	7, y	1, y	6, x	6, x

Пусть исходный автомат начинает свою работу из 1 состояния.

bbabaab – слово, которое дано по условию.

Строим таблицу, представленную ниже. В верхнюю строку записываем слово, которое дано по условию. В ячейку слева ставим 1. Это наше начальное состояние, из которого будет работать автомат.

	b	b	a	b	a	a	b
1

Далее эту таблицу нам нужно заполнить.

Начинаем заполнять сразу ячейку во второй строке. Затем ячейку ниже, и перемещаемся правее.

Для этого по таблице исходного автомата смотрим:

1)Ячейка (1,b).

A/Q	1
a	2, x
b	3, x

3 – записываем во вторую строку на пересечении 1 и b.

x – записываем ниже под 3.

	b	b	a	b	a	a	b
1	3
	х

2) Ячейка (3,b)

A/Q	3
a	2, x
b	1, x

Записываем во вторую строку 1, ниже – x.

	b	b	a	b	a	a	b
1	3	1
	х	x

3) Ячейка (1,а)

A/Q	1
a	2, x
b	3, x

Записываем во вторую строку 2, ниже – х.

	b	b	a	b	a	a	b
1	3	1	2
	х	x	х

4) Ячейка (2,b)

A/Q	2
a	4, x
b	6, x

Записываем в вторую строку 6, ниже – х.

	b	b	a	b	a	a	b
1	3	1	2	6
	х	x	х	х

5) Ячейка (6,а)

A/Q	6
a	9, y
b	7, y

Записываем в вторую строку 9, ниже – y.

	b	b	a	b	a	a	b
1	3	1	2	6	9
	х	x	х	х	y

6) Ячейка (9,а)

A/Q	9
a	7, x
b	6, x

Записываем в вторую строку 7, ниже – х.

	b	b	a	b	a	a	b
1	3	1	2	6	9	7
	х	x	х	х	y	х

Материал: PZ_14_dlya_studentov