|
Мінімізувати скінчений автомат з таблицею переходів:
S | |||||||
X | |||||||
Y |
Q={1,2,3,4,5,6,7}, S={X,Y}, q0=1, F={2,5}.
Алгоритм. Нахождение множества вершин, достижимых из данной вершины графа а (ориентированного) графа.
Вход. Граф G = (A, R), вершина aÎA.
Выход. Множество таких вершин bÎA, что aR+b
Метод. Будет образован список L, меняющийся в ходе работы алгоритма. Кроме того, будут отмечаться некоторые элементы множества А. Вначале все элементы из А не отмечены.
(1) Положить L = a
(2) Если список L пуст, остановиться. В противном случае вычеркнуть из L первый элемент b и отметить его в A.
(3) Поместить в конец списка L все неотмеченные элементы c из A, для которых bRc и перейти к шагу 2.
Для любых состояний q1 и q2:
(1) q1 º0 q2 тогда и только тогда, когда q1 и q2 оба либо принадлежат, либо не принадлежат F,
(2) q1 ºk q2 тогда и только тогда, когда q1 ºk-1 q2 и d(q1,a)ºk-1 d(q2,a) для всех aÎS.
По данному конечному автомату М можно найти наименьший эквивалентный ему конечный автомат, исключив все недостижимые состояния. Лишние состояния определяются с помощью разбиения множества всех состояний на классы эквивалентности так, что каждый класс содержит неразличимые состояния и выбирается как можно шире. Потом из каждого класса берется один представитель в качестве состояния сокращенного, или приведенного, автомата. Таким образом можно сократить объем автомата М, если М содержит недостижимые состояния или два и более неразличимых состояний. [Далее приводится доказательство факта минимальности такого автомата]
Шаг 1. Удалить все недостижимые состояния.
Шаг 2. Строить отношения эквивалентности º0, º1,..., до тех пор, пока два из них не совпадут: ºk-1= ºk. Взять в качестве º отношение ºk.
Шаг 3. Построить конечный автомат M’=(Q’, S, d’, q0’, F’), где
(a) Q’ – множество классов эквивалентности отношения º (обозначим через [p] класс эквивалентности отношения º, содержащий состояние p),
(b) d’ ([p], a)=[q], если d(p, a)=q
(c) q0’ – это [q0],
(d) F’={ [q] | q Î F }
Решение задачи
Удаление недостижимых состояний. Согласно алгоритму – состояние 3 недостижимо.
0. {1, 4, 6, 7} {2, 5}
1. {1, 6, 7} {4} {2, 5}
2. {1} {6, 7} {4} {2, 5}
3. {1} {6, 7} {4} {2} {5}
4. {1} {6, 7} {4} {2} {5}
Получим следующий автомат.
d’ | [1] | [2] | [4] | [5] | [6] |
X | [4] | [1] | [2] | [6] | [6] |
Y | [1] | [5] | [1] | [5] | [6] |
M’=({[1], [2], [4], [5], [6]}, {X, Y}, d’, [1], {[2], [5]})
Задача СП-2
Сформулюйте алгоритм пошуку тупикових станів в скінченому автоматі.
Мінімізувати скінчений автомат з таблицею переходів:
S | |||||||
A | |||||||
b |
Q={1,2,3,4,5,6,7}, S={0,1}, q0=1, F={2,4,6}.
Поиск тупиковых состояний. Состояние называется тупиковым, если из него нельзя достичь конечного состояния. Пользуясь алгоритмом достижимости из задачи 1 для каждого состояния автомата найдем множество достижимых из него состояний. Если для какого-то конкретного состояния в этом множестве не оказалось конечных состояний, то данное состояние – тупиковое.
Дата добавления: 2015-09-12; просмотров: 18 | Поможем написать вашу работу | Нарушение авторских прав |