Детерминированные и недетерминированные автоматы

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

Автоматы A и A ' называются эквивалентными, если L (A) = L (A ').

Т е о р е м а 4.2. Для любого недетерминированного конечного автомата можно построить эквивалентный детерминированный конечный автомат.

Доказательство. Сначала заметим, что грамматика соответствует детерминированному автомату тогда и только тогда, когда в каждом ее правиле вида A ® a ₁ A ₁ |... | a_nA_n или A ® a ₁ A ₁ |... | a_nA_n | e выполняется условие: a_i ¹ a_j при i ¹ j. Поэтому достаточно преобразовать А-грамматику G = (N, T, P, S) к указанному виду. В процессе преобразования на грамматику будем смотреть, как на соответствующую систему уравнений.

Для каждого непустого подмножества { A ₁,..., A_n } множества N введем новый нетерминальный символ [ A ₁,..., A_n ] и определим его так, чтобы соответствующее уравнение имело вид [ A ₁,..., A_n ] = A ₁ È... È A_n. Для этого достаточно, как в доказательстве теоремы 3.10, задать правило [ A ₁,..., A_n ] ® r ₁ |... | r_n, где r_i - правая часть правила для A_i.

Теперь построим требуемую грамматику G ' = (N ', T, P ', S), где N ' получается из N добавлением определенных выше новых нетерминальных символов, а P ' получено следующим образом из P и правил для новых нетерминальных символов: в каждом правиле все члены вида aA ₁,..., aA_n с одним и тем же a Î T заменяются одним членом a [ A ₁,..., A_n ]. Таким правилам соответствует детерминированный автомат, эквивалентный исходному, т.к. a [ A ₁,..., A_n ] = aA ₁ È... È aA_n.


Так как не все нетерминальные [ A ₁,..., A_n ] достижимы из S, то при построении P ' достаточно включать только необходимые правила, начиная с правила для S.

Пример 4.3. Недетерминированный автомат, изображенный на следующем рисунке слева,

имеет соответствующую грамматику с правилами

q ₀ ® aq ₁ | bq ₂, q ₁ ® aq ₁ | aq ₃ | bq ₁ | bq ₂,
q ₂ ® aq ₁ | aq ₂ | bq ₂ | bq ₃, q ₃ ® aq ₃ | bq ₃ | e.

Преобразуем его в детерминированный автомат по методу теоремы 4.2. В новую грамматику войдет старое правило для q ₀, т.к. оно удовлетворяет условию детерминированности. Правило для q ₁ преобразуется к виду q ₁ ® a (q ₁ | q ₃) | b (q ₁ | q ₂), или q ₁ ® aq ₁₃ | bq ₁₂.

Аналогично получается правило для q ₂: q ₂ ® aq ₁₂ | bq ₂₃.

Для q ₁₃ = q ₁ | q ₃ правило имеет вид q ₁₃ ® aq ₁ | aq ₃ | bq ₁ | bq ₂ | bq ₃ | e, или, окончательно, q ₁₃ ® aq ₁₃ | bq ₁₂₃ | e, где q ₁₂₃ = q ₁ | q ₂ | q ₃. Аналогично, для q ₁₂ = q ₁ | q ₂, q ₂₃ = q ₂ | q ₃ и q ₁₂₃ правила (после преобразования) имеют вид q ₁₂ ® aq ₁₂₃ | bq ₁₂₃, q ₂₃ ® aq ₁₂₃ | bq ₂₃ | e, q ₁₂₃ ® aq ₁₂₃ | bq ₁₂₃ | e.

Диаграмма построенного детерминированного автомата изображена на том же рисунке справа.


Отметим, что, как видно из доказательства и примера, построенный детерминированный автомат при анализе цепочки как бы одновременно ведёт все пути её анализа исходным автоматом.

Дата добавления: 2014-01-07