Студопедия

КАТЕГОРИИ:


Архитектура-(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) конечное множество - алфавит внутренних состояний;

q0Q начальное состояние автомата;

FQ множество принимающих (допускающих, заключительных) состояний;

Φ :Q Ч (Σ {ε}) → 2Q функция переходов. Для a Σ значение Φ(q, a) - это множество состояний в каждое из которых может перейти автомат из состояния q, когда получает на вход символ a. Φ(q, ε) - это множество состояний в каждое из которых может перейти автомат из состояния q без чтения символа на входе.

Как и для детерминированных автоматов, функцию переходов можно представить с помощью набора команд-программы: для каждой пары qQ и aΣ и каждого состояния qΦ(q, a) в программу помещается команда qa → q, и для каждого состояния qΦ(q, ε) в программу помещается команда q → q. Отличие от детерминированного случая состоит в том, что для одной пары q Q и a Σ в программе может быть несколько команд вида qa → qили не быть ни одной такой команды. Кроме того, могут появиться ε-команды (пустые переходы) вида q → q, означающие возможность непосредственного перехода из q в q без чтения символа на входе.



При табличном задании функции Φ в таблице появляется (m + 1)-ый столбец, соответствующий пустому символу ε и на пересечении строки q и столбца a {ε})стоит множество состояний Φ(q, a).

Для недетерминированного автомата M =<Σ, Q, q0, Φ > в диаграмме DM=(Q, E) с выделенной начальной вершиной q0 и множеством заключительных вершин F ребра взаимно однозначно соответствуют командам: команде вида qa → q (a Σ) соответствует ребро (q, q), с меткой a, а команде вида q → q cоответствует ребро (q, q), с меткой ε.

Скажем, что заданный последовательностью ребер путь p = e1e2. . . eT в диаграмме DM несет слово w = w1w2. . . wt (t ≤ T ), если после удаления из него пустых ребер (т.е. ребер с метками ε) остается последовательность из t ребер p= метки которых образуют слово w, т.е. wi это метка ребра 1(≤i≤t). Очевидно, это эквивалентно тому, что последовательность меток на ребрах пути p имеет вид , где kj≥ 0 (j = 1, 2, . . . , t + 1) и t + .

Слово w переводит q в qв диаграмме DM, если в ней имеется путь из q в q который несет w.

На недетерминированные автоматы естественным образом переносится определение конфигураций и отношения перехода между ними.

Конфигурация НКА M =< Σ, Q, q0, F, Φ, > - это произвольная пара вида (q, w), в которой q Q и w . Определим отношение M перехода из одной конфигурации в другую за один шаг :

(q, w) M(q’, w’) (w = aw’ и q’ Φ(q, a)) или (w = w’ и q’ Φ(q, ε)).

Как и для ДКА, через M обозначим рефлексивное и транзитивное замыкание отношения M.

Внешне определение распознавания слов НКА совпадает с определением для ДКА.

НКА M распознает (допускает, принимает) слово w, если для некоторого q F (q’, w) M(q, ε) .

Язык LM, распознаваемый НКА M, состоит из всех слов, распознаваемых автоматом:

LM= {w | M распознает w}.

Отличие состоит в том, что у НКА может быть несколько различных способов работы (путей вычисления) на одном и том же входном слове w. Считаем, что НКА распознает (допускает, принимает) это слово, если хотя бы один из этих способов приводит в заключительное состояние из F .

Из определения диаграммы DM непосредственно следует, что НКА M распознает слово w, тогда и только тогда, когда существует такое заключительное состояние q F , что в диаграмме DM слово w переводит q0 в q. Иными словами, в DM имеется путь из q0 в q, на ребрах которого написано слово w ( с точностью до меток ε).

Пример 1. Рассмотрим НКА N1=<{a,b},{0,1,2,3,4},0,{3},Φ>, где его диаграмма DN1 представлена на рис. 5.15.

 

Рис. 5.15. Таблица функции переходов и диаграмма НКА

 

Рассмотрим работу этого автомата на слове ababa:

Так как 3 - заключительное состояние, то ababa LN1. Заметим, что у автомата N1 имеются и другие способы работы на этом слове, не ведущие к заключительному состоянию. Например, он может после чтения каждого символа оставаться в состоянии 0. Но чтобы слово допускалось, достаточно существовать хотя бы одному хорошему способу.

 





Дата добавления: 2014-01-05; Просмотров: 483; Нарушение авторских прав?;


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Читайте также:



studopedia.su - Студопедия (2013 - 2017) год. Не является автором материалов, а предоставляет студентам возможность бесплатного обучения и использования! Последнее добавление ‚аш ip: 54.198.118.102
Генерация страницы за: 0.101 сек.