예. 정규식 go*d는 패턴이 gd, god, good ...패턴 검색에 사용되는 DFA는 무엇입니까?
같은 문자열을 일치합니다 그리고 당신은 DFA는 3 상태 머신과 같은 것입니다 상상할 수있다.
패턴 검색에 사용되는 경우. 주어진 문장 xxxxgodxxxxgoodxxx, go*d의 DFA가 작동하지 않는 것 같습니다. 문자 x도이 3- 상태 DFA에서 정의되지 않습니다.
추가 "재설정"상태가있는 4 상태 DFA가 여기에서 작동 할 수 있습니다. 즉, 정의되지 않은 문자가있는 경우이 "재설정"상태로 이동하십시오.
질문은 패턴 검색 도구가 go*d과 같은 정규식을 사용하여 검색 목적을 달성하는 방법입니까?
당신이 리셋 상태지만 [^g]으로 표시하여 시작 상태에 포괄 재귀 전환을 필요로하지 않는 사소한 3 주 정규
|start|---/g/---+->|S1|-->-+---/d/--->|accept|
| |
+--<-/o/-<-+
주어진다. dfa 정의를 엄격하게 따르는 경우 g이 아닌 하나의 알파벳 문자로 각각 라벨이 지정된 |Σ|-1 전환이 필요합니다. 마찬가지로 S1에서 start으로 표기된 [^g] 및 S1에서 g으로 레이블 된 표식으로의 전환은 패턴의 가능한 인스턴스화 접두어를 만나면 적절한 '재설정'을 보장합니다. 동일한 패턴에 대한 모든 인스턴스화 인 모든 중첩되지 않는 패턴 인스턴스화를 잡아낼 수 있습니다.
물론이 장난감 예제보다 훨씬 복잡해지기 때문에 표준 정규식 - 일반적으로 nfa-> dfa 구조가 사용됩니다 start 상태를 벗어날 때마다 개선없이 원래의 dfa를 취하여 서브 프로세스를 생성하는 전략이 있습니다. 서브 프로세스는 부모와 동일한 dfa를 주어진 것에 적용합니다. 전환 한 캐릭터로 시작하는 문장이 시작 상태로 유지됩니다.
이 소리 이전 질문과 비슷합니다. http://stackoverflow.com/questions/15489338/difference-between-pattern-matching-and-pattern-searching-inter-terms-of-dfa-regex. –
@OliCharlesworth 그들은 관련되어 있습니다. 그러나이 질문은 주어진 검색 정규 표현식에 대한 구현 전략에 관한 것입니다. 이전 질문은 검색과 일치의 일반적인 차이점에 대한 것입니다. 이전 것을 해결하면 도움이 될 것입니다. – JackWM