Что такое DFA, используемый для поиска шаблонов?

Question

E.g. регулярное выражение go*d это шаблон будет соответствовать строки как gd, god, good ...

И вы можете себе представить его DFA будет как 3-государственной машине.

Когда он используется для поиска по шаблону, например. данное предложение xxxxgodxxxxgoodxxx, DFA go*d, похоже, не сработает. Даже символ x не определен в этом DFA с 3 состояниями.

Мы можем представить себе, что здесь может работать DFA с 4 состояниями с дополнительным «сбросом» состояния. То есть, когда встречается неопределенный символ, перейдите в это состояние «перезагрузки».

Вопрос в том, как инструмент поиска по шаблону достигает цели поиска с регулярным выражением, например go*d?

Answer 1

дана тривиальная 3-состояние согласовань

|start|---/g/---+->|S1|-->-+---/d/--->|accept| 
       |   | 
       +--<-/o/-<-+ 

вам не нужен состояние сброса, но всеобъемлющий все рефлексивный переход на вашем начальном состоянии, меченный [^g]. строго следуя определению dfa, вам понадобится |Σ|-1 переходов, каждый из которых имеет один символ алфавита, отличный от g. аналогично переходы от S1 до start с пометкой [^g] и от S1 на себя с надписью g гарантируют правильное 'сброс' после обнаружения префиксов возможных экземпляров шаблона. улучшите состояние accept аналогично, и вы поймаете все неперекрывающиеся шаблонные экземпляры (которые являются все экземплярами для этого конкретного шаблона).

, конечно, это быстро становится намного сложнее, чем в этом примере игрушек, поэтому стандартное регулярное выражение-> nfa-> dfa обычно используется.

Другая стратегия заключалась бы в том, чтобы взять ваш оригинальный dfa без улучшений и вызвать подпроцесс каждый раз, когда вы покидаете состояние start. Подпроцесс применяет тот же самый dfa, что и его родитель, применяя его к данному предложение, начинающееся с символа, который сделал переход, покинул огонь начального состояния.