В практике разработки языков программирования, моделирование НКА оказывается несколько неэффективным по сравнению с ДКА. Поэтому оправданным оказывается построение ДКА, эквивалентного данному НКА, либо построение ДКА непосредственно. Мы рассмотрим первый подход.

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

ДКА можно рассматривать как частный случай НКА, в котором:

1. Нет переходов по \(ε\)
2. Для каждого состояния \(s\) и символа \(a\) имеется только один переход из \(s\) по \(a\).

Моделирование ДКА

В то время как НКА является скорее абстрактным представлением алгоритма распознавания строк, и как следствие, достаточно сложно реализуется напрямую, ДКА – простой, прямолинейный, и детерминированный алгоритм.

Модель ДКА можно реализовать, например, как

s = s₀;
c = nextChar();
while (c != eof) {
  s = move(s, c);
  c = nextChar();
}
if (s ∈ F) accept();
else reject();

Здесь \(move : (S, Σ) → S\) – функция, возвращающая для текущего состояния \(s \in S\) и символа \(c \in \Sigma\) следующее состояние \(s \in S\).

Переход от НКА к ДКА

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

Алгоритм построения эквивалентного ДКА можно записать следующим образом:

Dstates = [ε⁺(s₀)]
while(в Dstates есть непомеченное состояние T) {
  Пометить T;
  for (a ∈ Σ) {
    U = ε⁺(move(T, a));
    if (U ∉ Dstates) {
      Добавить U в Dstates как непомеченное;
    }
    Dtran[T, a] = U;
  }
}

Алгоритм строит множество состояний ДКА Dstates и таблицу переходов Dtran.

Распознавание шаблонов при помощи ДКА

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

Можно выразить этот алгоритм при помощи следующего псевдокода:

function getNextToken(inputBuffer) {
  state = 0; // начальное состояние ДКА == 0
  lastAccepting = -1;
  lastPos = -1;

  // тупиковое состояние ДКА == -1
  // pos -- позиция во входном буфере
  for(pos=0; state>=0; pos++){
    if (state -- принимающее) {
      // сохраняем последнее принимающее состояние
      lastAccepting = state;
      // и позицию, на которой оно достигнуто
      lastPos = pos;
    }
    // подсмотреть символ с номером pos во входном буфере
    // если входной буфер закончился, то peek вернёт EOF
    currentChar = inputBuffer.peek(pos);
    // dfaTransition -- таблица переходов
    state = dfaTransition(state, currentChar);
  }
  if (lastAccepting >= 0) {
    // убрать из буфера первых lastPos символов
    // и сохранить их в tokenStr
    tokenStr = inputBuffer.take(lastPos);
    return идентификатор токена, соотвтествующий lastAccepting
      и tokenStr;
  } else {
    сообщить об ошибке;
  }
}

Эффективность ДКА и НКА

Алгоритм преобразования НКА в ДКА может в худшем случае приводить к экспоненциальному росту числа состояний, и, соответственно, времени выполнения, \(O(|r|^2 2^{|r|})\). Однако, для типичных лексик, сложность построения ДКА не превышает \(O(|r|^3)\), где \(|r|\) – длина соответствующего регулярного выражения. Построение НКА значительно проще, и составляет \(O(|r|)\).

В то же время, сложность моделирования НКА зависит от размера НКА, а не только от размера входной строки, т.е. \(O(|r|\cdot|x|)\), где \(|x|\) – длина входной строки. В то время как сложность моделирования ДКА практически не зависит от размера автомата и определяется только входной строкой, \(O(|x|)\)

Отсюда можно сделать следующий вывод. Если регулярное выражение предполагается менять часто (например, по запросу пользователя), более целесообразным будет использовать алгоритм на основе НКА. Если же регулярное выражение будет меняться намного реже, чем использоваться (как, например, в случае лексического анализатора) – целесообразно использовать алгоритм на основе ДКА.