Какой DFA используется для поиска по шаблону?

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

И вы можете себе представить, что его DFA будет похож на автомат с тремя состояниями.

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

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

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


regex pattern-matching dfa finite-automata
person JackWM    schedule 19.03.2013    source источник
comment
Это очень похоже на ваш предыдущий вопрос: stackoverflow.com/questions/15489338/.   -  person Oliver Charlesworth    schedule 19.03.2013
comment
@OliCharlesworth Они связаны. Но этот вопрос касается стратегии реализации данного поискового регулярного выражения. Предыдущий вопрос касается общей разницы между поиском и сопоставлением. Решение предыдущей может помочь этой.   -  person JackWM    schedule 19.03.2013

Ответы (1)


arrow_upward
0
arrow_downward

учитывая тривиальный сопоставитель с 3 состояниями

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

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

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

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

person collapsar    schedule 27.03.2013