Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Сформулюйте алгоритм пошуку недосяжних станів в скінченому автоматі.

Мінімізувати скінчений автомат з таблицею переходів:

 

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; просмотров: 20 | Поможем написать вашу работу | Нарушение авторских прав

Задача БД-5 | Задача БД-14 | Задача ШІ-2 | Задача ОГ-1 | Задача ОГ-2 | Сформулюйте алгоритм пошуку e-нетерміналів для КВ-граматики. | Сформулюйте алгоритм пошуку множини ліворекурсивних нетерміналів. | Сформулюйте алгоритм пошуку Follow k(Аi), АiÎ N. | Задача ТО-2 |


lektsii.net - Лекции.Нет - 2014-2024 год. (0.007 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав