![]() КАТЕГОРИИ: ![]() Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Основные понятия недетерминированных конечных автоматовТема 5.3. Недетерминированные конечные автоматы Резюме по теме Вопросы для повторения
1.Детерминированный конечный автомат это? 2.Что называется диаграммой автомата? 3.Под программой автомата понимается? 4.В каком случае язык называется конечно-автоматным?
Приведены основные понятия детерминированных конечных автоматов. Выявлено понятие программы автомата, а так же диаграммы и конфигурации детерминированного автомата. Рассмотрена схема доказательства правильности автомата, которая позволяет судить о работоспособности автомата. Продемонстрировано произведение автомата.
Цель: ознакомиться с недетерминированными конечными автоматами и способом их детерминизации. Задачи: 1. Рассмотреть недетерминированные конечные автоматы. 2. Рассмотреть детерминизацию недетерминированного конечного автомата.
Рассматриваемые недетерминированные конечные автоматы являются обобщениями детерминированных: они при чтении очередного символа на входе могут выбрать в качестве следующего одно из нескольких состояний, а кроме того, могут изменить состояние без чтения входа. Основной результат, который мы установим, утверждает, что это обобщение не существенно: недетерминированные и детерминированные конечные автоматы распознают одни и те же языки. Недетерминированный конечный автомат (НКА) - распознаватель - это система вида M =< Σ, Q, q0, F, Φ >, включающая следующие компоненты: Σ = {a1, . . . , am} (m ≥ 1) конечное множество - входной алфавит; Q = {q0, . . . , qn−1}(n ≥ 1) конечное множество - алфавит внутренних состояний; q0 F Φ :Q Ч (Σ Как и для детерминированных автоматов, функцию переходов можно представить с помощью набора команд-программы: для каждой пары q При табличном задании функции Φ в таблице появляется (m + 1)-ый столбец, соответствующий пустому символу ε и на пересечении строки q и столбца a Для недетерминированного автомата M =<Σ, Q, q0, Φ > в диаграмме DM=(Q, E) с выделенной начальной вершиной q0 и множеством заключительных вершин F ребра взаимно однозначно соответствуют командам: команде вида qa → q’ (a Скажем, что заданный последовательностью ребер путь p = e1e2. . . eT в диаграмме DM несет слово w = w1w2. . . wt (t ≤ T ), если после удаления из него пустых ребер (т.е. ребер с метками ε) остается последовательность из t ребер p’= Слово w переводит q в q’в диаграмме DM, если в ней имеется путь из q в q’ который несет w. На недетерминированные автоматы естественным образом переносится определение конфигураций и отношения перехода между ними. Конфигурация НКА M =< Σ, Q, q0, F, Φ, > - это произвольная пара вида (q, w), в которой q (q, w) Как и для ДКА, через Внешне определение распознавания слов НКА совпадает с определением для ДКА. НКА M распознает (допускает, принимает) слово w, если для некоторого q Язык LM, распознаваемый НКА M, состоит из всех слов, распознаваемых автоматом: LM= {w | M распознает w}. Отличие состоит в том, что у НКА может быть несколько различных способов работы (путей вычисления) на одном и том же входном слове w. Считаем, что НКА распознает (допускает, принимает) это слово, если хотя бы один из этих способов приводит в заключительное состояние из F . Из определения диаграммы DM непосредственно следует, что НКА M распознает слово w, тогда и только тогда, когда существует такое заключительное состояние q
Рис. 5.15. Таблица функции переходов и диаграмма НКА
Рассмотрим работу этого автомата на слове ababa: Так как 3 - заключительное состояние, то ababa
Дата добавления: 2014-01-05; Просмотров: 790; Нарушение авторских прав?; Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет
Рекомендуемые страницы:
Читайте также:
|