Алгоритм построения детерминированного КА по НКА

Вход : M = (K, VT, F, H, S) - недетерминированный конечный автомат.

Выход : M’ = (K’, VT, F’, H’, S’) - детерминированный конечный автомат, допускающий тот же язык, что и автомат М.

Метод :

1. Множество состояний К’ состоит из всех подмножеств множества К. Каждое состояние из К’ будем обозначать A₁A₂...A_n, где A_i Î K.

2. Функции переходов F’ определим как F’ (A₁A₂...A_n, t) = B₁B₂...B_m, где для каждого 1 <= j <= m F(A_i, t) = B_j для каких-либо 1 <= i <= n.

3. Пусть H = {H₁, H₂, ..., H_k}, тогда H’ = H₁, H₂, ..., H_k.

4. Пусть S = {S₁, S₂, ..., S_p}, тогда S’ - все состояния из K’, имеющие вид ...S_i..., S_i Î S для какого-либо 1 <= i <= p.

Замечание: в множестве K’ могут оказаться состояния, которые недостижимы (см. Преобразования грамматик) из начального состояния, их можно исключить.

Проиллюстрируем работу алгоритма на примере.

Пусть задан НКА: M = ({H, A, B, S}, {0, 1}, F, {H}, {S}), где

F(H, 1) = B F(B, 0) = A

F(A, 1) = B F(A, 1) = S ,

тогда соответствующий детерминированный конечный автомат будет определен следующим образом.

Новое множество состояний ДКА: K’ = {H, A, B, S, HA, HB, HS, AB, AS, BS, HAB, HAS, ABS, HBS, HABS}

Множество входных сигналов и начальное состояние состояние автомата останутся неизменными.

Новое множество функций переходов:

F’(A, 1) = BS F’(H, 1) = B

F’(B, 0) = A F’(HA, 1) = BS

F’(HB, 1) = B F’(HB, 0) = A

F’(HS, 1) = B F’(AB, 1) = BS

F’(AB, 0) = A F’(AS, 1) = BS

F’(BS, 0) = A F’(HAB, 0) = A

F’(HAB, 1) = BS F’(HAS, 1) = BS

F’(ABS, 1) = BS F’(ABS, 0) = A

F’(HBS, 1) = B F’(HBS, 0) = A

F’(HABS, 1) = BS F’(HABS, 0) = A

Новое множество конечных состояний: S’ = {S, HS, AS, BS, HAS, ABS, HBS, HABS}

Достижимыми состояниями в получившемся КА являются H, B, A и BS, т.к. к ним возможен переход из других состояний, поэтому остальные состояния и соответствующие им функции переходов удаляются.

Таким образом, M’ = ({H, B, A, BS}, {0, 1}, F’, H, {BS}), где

F’(A, 1) = BS F’(H, 1) = B

F’(B, 0) = A F’(BS, 0) = A

Моделировать работу детерминированного КА существенно проще, чем произвольного КА, но при выполнении преобразования число состояний автомата может существенно возрасти и, в худшем случае, составит (2ⁿ - 1), где n - количество состояний исходного КА. В этом случае затраты на моделирование детерминированного КА окажутся больше, чем на моделирование исходного КА. Поэтому не всегда выполнение преобразования автомата к детерминированному виду является обязательным.

В некоторых случаях контекстно-свободная грамматика может содержать недостижимые символы, которые не участвуют в порождении цепочек языка и поэтому могут быть удалены из грамматики.

Символ x Î V называется недостижимым в грамматике G = (VT, VN, P, S), если он не появляется ни в одной сентенциальной форме этой грамматики, т.е. к нему не существует ни одного перехода на диаграмме состояний

Недостижимые символы удаляются из списка состояний КА и также удаляются все функции переходов этих символов.

 

Таблица свёрток и диаграмма состояний

Для того, чтобы при лексическом разборе быстрее находить правило с подходящей правой частью, фиксируют все возможные свертки в описании грамматики (это определяется только грамматикой и не зависит от вида анализируемой цепочки).

Это можно сделать в виде таблицы, строки которой помечены нетерминальными символами грамматики, столбцы - терминальными. Значение каждого элемента таблицы - это нетерминальный символ, к которому можно свернуть пару "нетерминал-терминал", которыми помечены соответствующие строка и столбец.

Например, для грамматики G = ({a, b, #}, {S, A, B, C}, P, S), такая таблица будет выглядеть следующим образом:

P: S ® C#

C ® Ab | Ba

A ® a | Ca

B ® b | Cb

 

Знак "-" ставится в том случае, если для пары "терминал-нетерминал" свертки нет.

 

Чаще информацию о возможных свертках представляют в виде диаграммы состояний - неупорядоченного ориентированного помеченного графа, который строится следующим образом:

(1) строят вершины графа, помеченные нетерминалами грамматики (для каждого нетерминала - одну вершину), и еще одну вершину, помеченную символом, отличным от нетерминальных, - H. Эти вершины будем называть состояниями. H - начальное состояние.

(2) соединяем эти состояния дугами по следующим правилам:

a) для каждого правила грамматики вида W ® t соединяем дугой состояния H и W (от H к W) и помечаем дугу символом t;

б) для каждого правила W ® Vt соединяем дугой состояния V и W (от V к W) и помечаем дугу символом t.

Диаграмма состояний для грамматики G (см. пример выше):

 

Тогда для диаграммы состояний применим следующий алгоритм разбора:

(1) объявляем текущим состояние H;

(2) затем многократно (до тех пор, пока не считаем признак конца цепочки) выполняем следующие шаги: считываем очередной символ исходной цепочки и переходим из текущего состояния в другое состояние по дуге, помеченной этим символом. Состояние, в которое мы при этом попадаем, становится текущим.

 

При работе этого алгоритма возможны следующие ситуации (аналогичные ситуациям, которые возникают при разборе непосредственно по регулярной грамматике):

(1) прочитана вся цепочка; на каждом шаге находилась единственная дуга, помеченная очередным символом анализируемой цепочки; в результате последнего перехода оказались в состоянии S. Это означает, что исходная цепочка принадлежит L(G).

(2) прочитана вся цепочка; на каждом шаге находилась единственная "нужная" дуга; в результате последнего шага оказались в состоянии, отличном от S. Это означает, что исходная цепочка не принадлежит L(G).

(3) на некотором шаге не нашлось дуги, выходящей из текущего состояния и помеченной очередным анализируемым символом. Это означает, что исходная цепочка не принадлежит L(G).

(4) на некотором шаге работы алгоритма оказалось, что есть несколько дуг, выходящих из текущего состояния, помеченных очередным анализируемым символом, но ведущих в разные состояния. Это говорит о недетерминированности разбора. Анализ этой ситуации будет приведен далее.

 

⇐ Предыдущая567891011121314Следующая ⇒

Поделиться: