Недетерминированные конечные автоматы

ЛЕКЦИЯ 5. 8.1. НЕДЕТЕРМИНИРОВАННЫЕ КОНЕЧНЫЕ АВТОМАТЫ 8.1.1. Вернёмся к примеру 7.3.-1 (лекция 4): автомат должен распознать слова, которые заканчиваются последовательностью 0110. Информация, которая понадобилась для синтеза автомата может быть изображена в виде следующей диаграммы успешного пути. Петля у начальной вершины – это любая возможная пред-история. Это диаграмма недетерминированного конечного автомата. Перейдём к точным определениям. 8.1.2. Определения. Недетерминированный конечный автомат (НКА) − это пятёрка H =(A,Q,Δ,S,F), где A − конечный алфавит, Q − конечное множество, элементы которого называются состояниями, S − начальные состояния, S  Q, S. F – финальные (заключительные) или допускающие состояния, F  Q, Δ − конечное множество отношений, Δ  Q×A*×Q, если (p,ã,q)Δ, то (p,ã,q) называется переходом из p в q, слово ã − меткой этого перехода. 8.1.3. Конечные автоматы, которые рассматривались выше, будем называть детерминированными (ДКА). Разберёмся с отличиями этого определения от определения конечного автомата (детерминированного) без выхода (см. п.7.3.6, лекция 4) D=(A,Q,g,q0,F). Функция g : Q×A → Q определяла для каждого состояния q и каждого символа a в точности один переход из q, помеченный символом a. В НКА определено множество отношений ΔQ×A*×Q, не обладающее таким свойством однозначности: для любого состояния может быть определён более чем один переход с одной и той же меткой, может не быть переходов (например для финальных состояний), меткой перехода может быть слово, а значит меткой перехода может быть пустое слово. В отличие от инициального ДКА с одним начальным состоянием q0 в НКА может быть не одно начальное состояние. 8.1.4. НКА может быть сопоставлен ориентированный размеченный граф G=(A,Q,Δ,S,F). Любому конечному пути в этом графе приписываем одно слово, читая символы вдоль этого пути. Путь называется успешным, если его начало принадлежит S, а конец принадлежит F. Слово ã допускается конечным недетерминированным автоматом H, если оно является меткой некоторого успешного пути. Язык, распознаваемый НКА автоматом H, − это язык L(H), состоящий из меток всех успешных путей (то есть из всех допускаемых данным автоматом слов). Язык L называется автоматным, если существует НКА распознающий этот язык. 8.1.5. Лемма. Каждый автоматный язык распознаётся некоторым конечным автоматом, не содержащим переходов с метками длины больше единицы и имеющим ровно одно начальное состояние. (Любой НКА можно преобразовать в автомат с одним начальным состоянием, используя пустые переходы.) 8.1.6. Теорема. Класс автоматных языков замкнут относительно объединения, катенации, итерации. Эти три операции в совокупности называют регулярными. Доказательство. Без ограничения общности можно предположить, что каждый из исходных языков задан конечным автоматом с одним начальным и одним финальным состоянием. o Объединение: L(H)=L₁(H₁)L₂(H₂), результирующий автомат H получается, если совместить начальные и финальные состояния автоматов H₁ и H₂ o Катенация: L(H)=L₁(H₁)L₂(H₂) − финальное состояние автомата H₁ и начальное состояние H₂ совмещаются. o Итерация: L*(H) − начальные и финальные состояния автомата H совмещаются, а затем разъединяются с использованием дуг (переходов), помеченных пустым словом. 8.1.7. Каждый автоматный язык распознаётся некоторым детерминированным конечным автоматом. Иначе говоря, для любого НКА может быть построен ДКА. Метод состоит в построении взаимно-однозначного соответствия подмножества состояний НКА состояниям ДКА. При выполнении вычислений синхронным автоматом, абстрактной моделью которого является, конечно, ДКА, может существовать только один последовательный процесс, каждому шагу (такту) которого соответствует только одно состояние автомата. В НКА можно считать, что так же существует один последовательный процесс, который в любом такте может находиться более чем в одном состоянии НКА. Все те состояния НКА, которые в какомлибо такте могли быть использованы одновременно, сопоставляются единственному состоянию ДКА. Это можно сделать, если проследить все возможные варианты развития последовательных процессов в НКА. 8.1.8. Преобразуем НКА из п. 8.1.1 в ДКА. НКА QН 1 2 3 F Fl 0,1 F 1 1 2 3 ε ДКА № 1 2 3 4 5 QД 0,1 0,2 0,3 0,1,F Fl 1 0,1 0,1 0,1 0,1,F 0,1 1 0,2 0,3 0,2 Получили ДКА изоморфный автомату из примера 7.3.-1 (лекция 4). Пример 8.1.-1. Спроектировать автомат, который устанавливает на выходе 1, если слово заканчивается последовательностью, в которой между двумя нулями содержится чётное число единиц (число ноль чётное). Диаграмма НКА: В диаграмме есть переходы по пустой метке (метка ε – пустое слово). Приведём универсальный алгоритм преобразования НКА в ДКА. 8.1.9. Алгоритм преобразования НКА в ДКА. Будем называть состояния НКА вершинами, состояния ДКА состояниями. 0) «Чистка» НКА (не обязательное действие, но сокращающее трудоёмкость алгоритма детерминизации). Из НКА удаляются: − петли без меток; − вершины, недостижимые из начальных вершин; − вершины, из которых недостижимы заключительные вершины. 1) Таблица НКА. В таблице должны быть следующие столбцы: − имя вершины, − индекс вершины, − индикатор (флаг) финальной вершины, остальные столбцы соответствуют всем символам входного алфавита плюс пустой символ. Первая строка таблицы соответствует единственной входной вершине. Если входных вершин было более одной, то это будет новая вершина, которая соединяется дугами без меток (пустой меткой) со всеми старыми входными вершинами. Остальные строки соответствуют всем вершинам НКА. 2) Нумерация дуг (переходов). Каждый помеченный переход получает уникальный номер, начиная с 2 и далее 3,4,... 3) Индексация вершин. Входная вершина получает индекс 1. Вершинам НКА присваивается индекс, состоящий из номеров всех входящих в эту вершину дуг. Индекс вершины, из которой выходит пустая дуга, приписывается к индексу вершины, в которую эта дуга входит. 4) Автоматная таблица. Заготавливается таблица (пустая), в которой должны быть следующие столбцы: − шифр состояния, − флаг финальных вершин, − остальные столбцы соответствуют всем символам входного алфавита. 5) Заполнение строки автоматной таблицы. Первой строке, соответствующей начальному состоянию автомата, присваивается шифр 1. Начиная с этой строки, используя таблицу источника, в столбцы, именованные входными символами, записываются номера дуг, имеющих метку, совпадающую с именем столбца и выходящих из всех вершин, в индексах которых содержится какой-либо номер из шифра этого состояния (строки). Если таких дуг нет, то записывается номер 0. В строке с шифром 0 во всех столбцах содержатся нули. (Состоянию с шифром 0 соответствует “тупиковое” состояние.) 6) Порождение новых строк. После заполнения очередной строки в столбцах, именованных входными символами, записаны шифры состояний. Если в строке появились новые шифры, не встречавшиеся ранее, то они порождают новые строки. 7) Финальным будет то состояние, в шифре которого есть номер, совпадающий с каким-либо номером из индексов финальных вершин НКА. А теперь преобразуем НКА примера 8.1-1 в ДКА. НКА V Fl 0,1\2 1 2 3 4 F\6 F 1 ДКА Q Fl 0 1 1 2 1 2 4 5 4 1 4 5 5 2 2 1 ε 0\3 2 3\4 4 2\5 индекс 1,2,3 2 2,5 4 2,5 6 ДКА Q 1 2 3 4 5 6 шифр Fl 1 2 3 2,6 3,4 3,5 1 2 2,6 2 2,6 2 2,6 1 3 3,4 3 3,4 3,5 3,4 ≡ 1≡3 2≡6 1≡3 2≡6