Материал: PZ_14_dlya_studentov

ПЗ 14. Теория конечных автоматов

Задача. Теория будет ниже.

Для конечного автомата, заданного таблично, со множеством состояний {1,2,3,4,5,6,7,8,9}, входным алфавитом {a,b} и выходным алфавитом {x, y}:

1. Построить эквивалентный минимальный автомат, изобразить в виде графа

2. Проверить работу исходного и минимального автоматов над словом «bbabaab».

Конечный автомат

Решение:

Шаг 1. Строим треугольную матрицу(таблицу) как показано ниже и заполняем её.

Снизу нумерация начинается с 1 и заканчивается n-1, где n- количество состояний (номер последнего столбца)

По вертикали слева начиная с 2 и до n.

Смотрим первый столбец исходной таблицы и сравниваем с каждым последующим.

На числа внимание не обращаем, сравниваем только буквы. Если буквы совпадают, то в соответствующую ячейку таблицы ничего не ставим, а если же значения не совпадают, то ставим крестик в треугольную матрицу соответствующей ячейки.

Первый столбец со вторым

Например, тут значения совпадают, следовательно, в ячейке (1,2) мы ничего не ставим.

1	2
2, x	4, x
3, x	6, x

Первый столбец с третьим

1	3
2, x	2, x
3, x	1, x

Тут значения совпали

Первый столбец с четвертым

1	4
2, x	2, x
3, x	3, y

Значения не совпали, следовательно, в ячейку (1,4) ставим крестик.

Так подробно далее рассматривать не будем.

! Обратите внимание, что каждый раз вы рассматриваем столбец только с теми столбцами, которые находятся правее. Так предыдущие пары столбцов мы уже рассмотрели.

1 столбец не совпал с 4,5,6,7, следовательно, в этих ячейка ставим крестики.

2 столбец не совпал с 4,5,6,7, следовательно, в этих ячейка ставим крестики.

3 столбец не совпал с 4,5,6,7, следовательно, в этих ячейка ставим крестики.

4 столбец не совпал с 6,8,9, следовательно, в этих ячейка ставим крестики.

5 столбец не совпал с 6,8,9, следовательно, в этих ячейка ставим крестики.

6 столбец не совпал с 7,8,9, следовательно, в этих ячейка ставим крестики.

7 столбец не совпал с 8,9, следовательно, в этих ячейка ставим крестики.

8 столбец осталось проверить только с 9 столбцом, они совпали, следовательно, ничего нового не ставим.

Так подробно расписывать в тетрадках не нужно. Строим сразу таблицу, показанную ниже.

Шаг 2. Заполняем пустые ячейки.

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

Ниже показаны наши столбцы 1 и 2.

Следовательно, в ячейку записываем только числа. Верхняя строка 2 4, нижняя 3 6.

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

Ниже показаны наши столбцы 1 и 2.

! Желтым выделены повторения по строкам. По диагонали мы не выделяем.

Шаг 3. Сортируем строки, убираем повторения.

Убираем из ячеек пары, которые совпадают с координатой ячейки.

Например

В ячейке (1,6) была пара 1,6, следовательно, полностью убираем все из этой ячейки.

Было:

Стало:

В данном примере у нас такой случай содержит ячейка (1,3), так как в ней есть пара 3,1. То, что она записана наоборот, ничего страшного. Нам она подходит, поэтому мы полностью. Очищаем эту клетку. Также убираем все повторения, которые в предыдущем шаге были выделены желтым. Из ячейки (8,9) вычеркнули два повторения.

Шаг 4. Зачеркиваем ячейки с проставленными числами, если в ячейке стоит пара, которая соответствует уже вычеркнутой ячейке.

Сейчас более подробно и понятно на примере.

Смотрим, какие значения у нас остались в ячейке (1,2). Остались пары 2,4 и 3,6. Смотрим, соответствует ли какая-нибудь из этих пар вычеркнутой ячейке. В данном случае и ячейка (2,4) является вычеркнутой, и ячейка (3,6) также зачеркнута. Следовательно, ячейку (1,2) зачеркиваем. Но нам достаточно было, чтобы хотя бы одна из этих пар соответствовала вычеркнутой ячейке.

Смело вычеркиваем все ячейки, в которых записаны пары 2,4 или 3,6.