2015-04-06
950
Недетерминированный конечный автомат (НКА) представляет собой математическую модель, состоящую из:
• множества состояний S;
• множества входных символов X (символов входного алфавита);
• функции переходов move, которая отображает пары символ-состояние на множество состояний;
• состояния s0, известного как стартовое (начальное);
• множества состояний F, известных как допускающие (конечные).
НКА может использоваться в виде помеченного ориентированного графа, так называемого графа переходов, узлы которого представляют собой состояния, а помеченные дуги составляют функцию переходов. Такой граф похож на диаграмму переходов, однако один и тот же символ может помечать два и более переходов из одного состояния, а некоторые переходы могут быть помечены специальным символом e как обычным входным символом (e-переходы).
Граф переходов для НКА, распознающего язык (a|b)*abb, показан на рис. 1.7. Множество состояний НКА – {0, 1, 2, 3}, а входной алфавит – {а, b}. Состояние 0 – стартовое, а заключительное состояние 3 представлено двойным кружком. 
|
|
|
При описании НКА воспользуемся графом переходов. Как мы увидим далее, функция переходов НКА может быть реализована различными способами. Простейший из них – таблица переходов, в которой строки представляют состояния, а столбцы – входные символы (и, при необходимости, e). Запись в строке i для символа а является множеством состояний (или – на практике – чаще всего указателем на множество состояний), которые могут быть достигнуты переходом из состояния i при входном символе а.
Алгоритм приведения грамматики к автоматному виду
Соглашение: предположим, что анализируемая цепочка заканчивается специальным символом ^ - признаком конца цепочки.
Для леволинейных грамматик существует алгоритм определения того, принадлежит ли анализируемая цепочка языку, порождаемому этой грамматикой (алгоритм разбора):
(1) первый символ исходной цепочки a1a2...an^ заменяем нетерминалом A, для которого в грамматике есть правило вывода A ® a1 (другими словами, производим "свертку" терминала a1 к нетерминалу A)
(2) затем многократно (до тех пор, пока не считаем признак конца цепочки) выполняем следующие шаги: полученный на предыдущем шаге нетерминал A и расположенный непосредственно справа от него очередной терминал ai исходной цепочки заменяем нетерминалом B, для которого в грамматике есть правило вывода B ® Aai (i = 2, 3,.., n);
Это эквивалентно построению дерева разбора методом "снизу-вверх": на каждом шаге алгоритма строим один из уровней в дереве разбора, "поднимаясь" от листьев к корню.
При работе этого алгоритма возможны следующие ситуации:
|
|
|
(1) прочитана вся цепочка; на каждом шаге находилась единственная нужная "свертка"; на последнем шаге свертка произошла к символу S. Это означает, что исходная цепочка a1a2...an^ Î L (G).
(2) прочитана вся цепочка; на каждом шаге находилась единственная нужная "свертка"; на последнем шаге свертка произошла к символу, отличному от S. Это означает, что исходная цепочка a1a2...an^ Ï L (G).
(3) на некотором шаге не нашлось нужной свертки, т.е. для полученного на предыдущем шаге нетерминала A и расположенного непосредственно справа от него очередного терминала ai исходной цепочки не нашлось нетерминала B, для которого в грамматике было бы правило вывода B ® Aai. Это означает, что исходная цепочка a1a2...an^ Ï L (G).
(4) на некотором шаге работы алгоритма оказалось, что есть более одной подходящей свертки, т.е. в грамматике разные нетерминалы имеют правила вывода с одинаковыми правыми частями, и поэтому непонятно, к какому из них производить свертку. Это говорит о недетерминированности разбора. Анализ этой ситуации будет дан ниже.
Допустим, что разбор на каждом шаге детерминированный.
Для того, чтобы быстрее находить правило с подходящей правой частью, зафиксируем все возможные свертки (это определяется только грамматикой и не зависит от вида анализируемой цепочки).
чаще информацию о возможных свертках представляют в виде диаграммы состояний (ДС) - неупорядоченного ориентированного помеченного графа, который строится следующим образом:
(1) строят вершины графа, помеченные нетерминалами грамматики (для каждого нетерминала - одну вершину), и еще одну вершину, помеченную символом, отличным от нетерминальных (например, H). Эти вершины будем называть состояниями. H - начальное состояние.
(2) соединяем эти состояния дугами по следующим правилам:
a) для каждого правила грамматики вида W ® t соединяем дугой состояния H и W (от H к W) и помечаем дугу символом t;
б) для каждого правила W ® Vt соединяем дугой состояния V и W (от V к W) и помечаем дугу символом t;
Диаграмма состояний для грамматики G (см. пример выше):
