- •Введение в дискретный анализ
- •Глава 1. Введение в теорию множеств
- •Тема 1.1. Множества и операции над ними
- •1.1.1. Основные понятия
- •1.1.2. Операции над множествами
- •1.1.3. Векторы и прямые произведения
- •Вопросы для повторения
- •Резюме по теме
- •Тема 1.2. Отношения
- •1.2.1. Основные понятия и определения
- •1.2.2. Бинарные отношения. Основные определения
- •1.2.4. Эквивалентность и порядок
- •Вопросы для повторения
- •Резюме по теме
- •Тема 1.3. Соответствия и функции
- •1.3.1. Соответствия и их свойства
- •1.3.2. Взаимно однозначные соответствия и мощности множеств
- •1.3.3. Функции и отображения
- •1.3.4. Операции
- •1.3.5. Гомоморфизмы и изоморфизмы
- •Вопросы для повторения
- •Резюме по теме
- •Глава 2. Математическая логика
- •Тема 2.1. Логика высказываний
- •2.1.1. Логические связки
- •2.1.2. Основные схемы логически правильных рассуждений
- •2.2.2. Булева алгебра
- •2.2.3. Эквивалентные преобразования
- •Вопросы для повторения
- •Резюме по теме
- •Тема 2.3. Полнота и замкнутость
- •2.3.1. Функционально полные системы
- •2.3.2. Алгебра Жегалкина и линейные функции
- •2.3.3. Замкнутые классы и монотонные функции
- •2.3.4. Теоремы о функциональной полноте
- •Вопросы для повторения
- •Резюме по теме
- •Тема 2.4. Нечеткая логика
- •2.4.1. Основные понятия теории нечетких множеств
- •2.4.2. Логические операции над нечеткими множествами
- •2.4.3. Свойства логических операций над нечеткими множествами
- •Вопросы для повторения
- •Резюме по теме
- •Тема 2.5. Нечеткие модели управления
- •2.5.1. Нечеткие операторы
- •2.5.2. Нечеткая и лингвистическая переменные
- •2.5.3. Нечеткий логический вывод
- •Вопросы для повторения
- •Резюме по теме
- •Тема 2.6. Логика предикатов
- •2.6.1. Предикаты. Основные понятия
- •2.6.2. Кванторы
- •2.6.3. Выполнимость и истинность
- •2.6.4. Эквивалентные соотношения. Префиксная нормальная форма
- •Вопросы для повторения
- •Резюме по теме
- •Глава 3. Комбинаторика
- •Тема 3.1. Комбинаторные конфигурации
- •3.1.1. Принципы сложения и умножения
- •3.1.2. Перестановки
- •3.1.3. Размещения
- •3.1.4. Сочетания
- •3.2.2. Полиномиальная формула
- •3.2.3. Формула включений и исключений
- •Вопросы для повторения
- •Резюме по теме
- •Глава 4. Теория графов
- •Тема 4.1. Основные понятия и операции на графах
- •4.1.1. Основные понятия
- •4.1.2. Способы задания графов
- •4.1.3. Операции над частями графа. Графы и бинарные отношения
- •Вопросы для повторения
- •Резюме по теме
- •Тема 4.2. Маршруты и деревья
- •4.2.1. Маршруты, пути, цепи, циклы
- •4.2.2. Дерево и лес
- •5.1.2. Способы задания автоматов
- •5.1.3. Взаимосвязь между моделями Мили и Мура
- •Вопросы для повторения
- •Резюме по теме
- •Тема 5.2. Детерминированные конечные автоматы
- •5.2.1.Основные понятия детерминированных конечных автоматов
- •5.2.2. Схема доказательства правильности конечного автомата
- •5.2.3. Произведение автоматов
- •5.3.2. Детерминизация нка
- •Вопросы для повторения
- •Резюме по теме
5.2.2. Схема доказательства правильности конечного автомата
Схема доказательства правильности конечного автомата такова:
1) определить (описать) для каждого состояния q Q язык L(q),состоящий из слов, переводящих начальное состояние q0 в q;
2) доказать, что это определение правильное, используя индукцию по длине входного слова;
3) показать, что .
Применим эту схему к доказательству правильности, построенного выше автомата A. Языки, связанные с состояниями этого автомата, фактически, уже были определены при его построении. Уточним их:
L(q0) = {ε},
L(q1) = {a},
L(q2) = {w | слова, начинающиеся с aa и содержащие четное число букв b},
L(q3) = L,
L(q!) = {w | слова, не начинающиеся с aa}.
Правильность определения языков L(q0), L(q1) и L(q1) следует непосредственно из определения A. Самое короткое слово, переводящее q0 в q2aa, и оно принадлежит L(q2). Аналогично, самое короткое слово, переводящее q0 в q3 aab, и оно принадлежит L(q3). Предположим теперь, что для каждого слова w длины ≤ n выполнено условие(*):
Покажем, что оно будет выполнено и для всех слов длины n + 1.
Пусть|w|=n+1. Тогда w=w’α, где α {a, b}. Так как |w’| = n, то для w’выполнено условие (*). Поэтому, если w’ переводит q0 в q2, то это слово начинается с aa и содержит четное число b. При α = a слово w переводит q0 в q2 и также начинается с aa и содержит четное число b, а при α = b слово w переводит q0 в q3, начинается с aa и содержит нечетное число b, т.е. принадлежитL.
Аналогично, если w’ переводит q0 в q3, то это слово начинается с aa и содержит нечетное число b. При α =a слово w также переводит q0 в q3 и также начинается с aa и содержит нечетное число b, а при α = b w переводит q0 в q2, оно начинается с aa и содержит четное число b. Обратно, если α= a, то слово w переводит q0 в qi (i = 2, 3) w’переводит q0 в qi(i = 2, 3) и условие (*) выполнено, так как четность числа букв b в w и в w’ одинакова. Если же α = b , то из определения автомата A следует, что слово w переводит q0в q2 w’ переводит q0 в q3и w переводит q0в q3 w’переводит q0 в q2. Так как четность числа букв b в w и в w0разная, то и в этом случае условие (*) выполнено. Для завершения доказательства осталось заметить, что единственным заключительным состоянием автомата A является q3 и поэтому LA= L(q3) = L.
5.2.3. Произведение автоматов
Рассмотрим одну важную конструкцию конечного автомата по двум другим, называемую произведением автоматов, которая позволит установить замкнутость класса конечно автоматных языков относительно теоретико множественных операций.
Пусть M1=< Σ, Q1, , ,Φ1> и M2=< Σ, Q2, , F2,Φ2> два конечных автомата с общим входным алфавитом Σ, распознающие языки L1 и L2, соответственно.
Определим по ним автомат M=< Σ, Q, q0, F, Φ >, называемый произведением M1 и M2(M = M1хM2), следующим образом. Q = Q1хQ2= {(q, p) | q Q1, p Q2}, т.е. состояния нового автомата это пары, первый элемент которых состояние первого автомата, а второй состояние второго автомата. Для каждой такой пары (q, p) и входного символа a Σ определим функцию переходов: Φ((q, p), a) =(Φ1(q, a), Φ2(p, a)). Начальным состоянием M является пара q0= ( , ), состоящая из начальных состояний автоматов-множителей. Что касается множества заключительных состояний, то оно определяется в зависимости от операции над языками L1 и L2, которую должен реализовать M .
Теорема 1.
а) При автомат M=<Σ, Q, q0, , Φ> распознает язык L = L1 L2.
б) При F∩={(q, p) | q F1 и p F2} автомат M =< Σ, Q, q0, F∩,Φ > распознает язык L = L1∩ L2.
в) При F\= {(q, p) | q F1 и p F2} автомат M =< Σ, Q, q0, F\, Φ > распознает язык L = L1\ L2.
Доказательство этой теоремы непосредственно выводится из следующего утверждения.
Лемма 2. Для любых двух состояний (q, p) и (q’, p’) автомата M и любого входного слова w слово w переводит (q, p) в (q’, p’) в автомате M тогда и только тогда, когда оно переводит q в q’ в автомате M1 и p в p’в автомате M2.
Лемма устанавливается индукцией по длине слова w.
Следствие. Класс конечно автоматных языков замкнут относительно теоретико множественных операций объединения, пересечения и разности.
Вопросы для повторения
1.Детерминированный конечный автомат это?
2.Что называется диаграммой автомата?
3.Под программой автомата понимается?
4.В каком случае язык называется конечно-автоматным?
Резюме по теме
Приведены основные понятия детерминированных конечных автоматов. Выявлено понятие программы автомата, а так же диаграммы и конфигурации детерминированного автомата. Рассмотрена схема доказательства правильности автомата, которая позволяет судить о работоспособности автомата. Продемонстрировано произведение автомата.
Тема 5.3. Недетерминированные конечные автоматы
Цель: ознакомиться с недетерминированными конечными автоматами и способом их детерминизации.
Задачи:
Рассмотреть недетерминированные конечные автоматы.
Рассмотреть детерминизацию недетерминированного конечного автомата.
5.3.1. Основные понятия недетерминированных конечных автоматов
Рассматриваемые недетерминированные конечные автоматы являются обобщениями детерминированных: они при чтении очередного символа на входе могут выбрать в качестве следующего одно из нескольких состояний, а кроме того, могут изменить состояние без чтения входа. Основной результат, который мы установим, утверждает, что это обобщение не существенно: недетерминированные и детерминированные конечные автоматы распознают одни и те же языки.
Недетерминированный конечный автомат (НКА) - распознаватель - это система вида
M =< Σ, Q, q0, F, Φ >,
включающая следующие компоненты:
Σ = {a1, . . . , am} (m ≥ 1) конечное множество - входной алфавит;
Q = {q0, . . . , qn−1}(n ≥ 1) конечное множество - алфавит внутренних состояний;
q0 Q начальное состояние автомата;
F Q множество принимающих (допускающих, заключительных) состояний;
Φ :Q Ч (Σ {ε}) → 2Q функция переходов. Для a Σ значение Φ(q, a) - это множество состояний в каждое из которых может перейти автомат из состояния q, когда получает на вход символ a. Φ(q, ε) - это множество состояний в каждое из которых может перейти автомат из состояния q без чтения символа на входе.
Как и для детерминированных автоматов, функцию переходов можно представить с помощью набора команд-программы: для каждой пары q Q и 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. Но чтобы слово допускалось, достаточно существовать хотя бы одному хорошему способу.