В идеале регулярное выражение (если оно является истинным регулярным выражением) сначала преобразуется в графическое представление NFA (недетерминированный конечный автомат), возможно, что-то вроде этого:
a(bc)*:
(0)-- a --> (1) ---b--> (2) -- ε --> ((3))
^ |
`-----c----'
0начальное состояние;((3)) является состоянием принятия. ε - пустой переход без использования входных данных.
NFA может быть выполнен непосредственно алгоритмом моделирования NFA.
Он также может быть скомпилирован в DFA (детерминированный FA) с использованием конструкции "подмножества"». Состояния DFA соответствуют наборам исходных состояний NFA. В итоге получается что-то вроде этого:
DFA state NFA States Input Next State
--------------------------------------------
0 { 0 } a 1
1 { 1 } b 2
2 (accept) { 2, 3 } c 1
Состояние 2 DFA соответствует двум состояниям NFA: когда DFA находится в состоянии 2, соответствующий имитатор NFA должен одновременно находиться в состояниях 2 и 3, потому что 3 достижимо через эпсилон-переход (входной символ не используется). Состояние DFA 2 является состоянием приема, поскольку набор NFA, соответствующий {2, 3}, содержит состояние приема.
DFA требует очень мало шагов;в основном мы просто читаем символы и отправляем в следующее состояние в таблице на основе текущего состояния и входного символа. Если мы не можем отправить, то есть несоответствие;мы можем перестать читать больше ввода. Если мы обработаем весь ввод и останемся в состоянии принятия, то будет совпадение.