Создание ДКА на основе регулярного выражения

1. дерево
2. набор позиций
3. nullable, множества firstpos и lastpos
4. множества followpos
5. генерация таблицы

nullable, множества firstpos и lastpos вычисляются для каждого узла дерева, а followpos вычисляется для каждой позиции.

Алгоритмы для nullable, firstpos и lastpos

A leaf labeled ε:

nullable(n) := true
firstpos(n) := {}
lastpos(n)  := {}

A leaf with position i:

nullable(n) := false
firstpos(n) := {i}
lastpos(n)  := {i}

An "or"-node c1 | c2:

nullable(n) := nullable(c1) or nullable(c2)
firstpos(n) := firstpos(c1) U firstpos(c2)
lastpos(n)  := lastpos(c1) U lastpos(c2)

A "cat"-node c1 c2:

nullable(n) := nullable(c1) and nullable(c2)
firstpos(n) := nullable(c1) ? firspos(c1) U firspos(c2) : firspos(c1)
lastpos(n)  := nullable(c2) ? lastpos(c1) U lastpos(c2) : lastpos(c2)

A "star"-node c1*:

nullable(n) := true
firstpos(n) := firstpos(c1)
lastpos(n)  := lastpos(c1)

При вычислении этих множеств рекурсия неприемлема, т.к. размер дерева может быть очень большим.

Алгоритм для followpos

for node n in tree:
  if n is concat node with left child c1 and right child c2:
    for i in lastpos(c1):
      followpos(i) = followpos(i) U firstpos(c2)
  else if n is Kleene star node:
    for i in lastpos(n):
      followpos(i) = followpos(i) U firstpos(n)

Алгоритм построения ДКА

s0 = firstpos(root-node); designate it the start state
states = [s0] and is unmarked

while there is an unmarked state T in states:
  mark T
  for each input symbol 'a' in the alphabet:
    let U be the union of followpos(p) for all positions p in T such that
            the symbol at position p is 'a'
    if U is not empty and not in states:
      add U as an unmarked state in states
    trans[T,a] = U

Designate any state containing the #-position as a final state