라인이 NFA와 일치하는지 어떻게 확인할 수 있습니까?

정규식 3d 배열 (예 : (01 *) 표현식)을 만드는 NFA를 만들었습니다. 알 겠어 :라인이 NFA와 일치하는지 어떻게 확인할 수 있습니까?

[[FROM,TO,TRANSITION]] 

    [['q0', 'q1', '0'], ['q1', 'q2', ':e:'] ,['q1', 'q4', ':e:'] , 
    ['q2', 'q3', '1'], ['q3', 'q2', ':e:'], ['q3', 'q4', ':e:']

이 오토 마톤을 만족하는 문자열을 테스트 할 수있는 방법을 어떻게 쓰나요? 예를 "011111"를 들어 (즉, 검사가 사소한 된 후) 당신은 DFA로 자동 장치를 변환 할 수 있습니다 q0 q1 q2 q3 q2 q3 q2 q3 q2 q3 q2 q3 q4

출처

2017-04-16 Eywa

글쎄, 오토 마톤이 결정 론적이라면 어떻게 할 수 있겠습니까? – timgeb

(해당하는 경우 DFA를 구성하는 알고리즘에 대해 foo 검색 엔진 적용) – timgeb

사용할 수있는 기존 라이브러리가 많으므로웨어를 다시 발명 할 필요가 없습니다. 업계에서 강력하고 사용하기 쉬운 Java 용 오토메이션 패키지 인 http://www.brics.dk/automaton/을 제안합니다. 그것은 당신이 원하는 것을 정확히 수행합니다. 또한 주어진 문자열과 일치시키기 위해 특정 전환이 수행되었는지에 대한 자세한 정보가 필요한 경우 Automaton 클래스를 확장하는 것이 매우 쉽습니다. – Julian

를 반환합니다. 이 접근법은 NFA가 작지만 테스트 할 문자열의 수가 아주 많기 때문에 유용합니다.
각 정점이 쌍 (NFA의 상태, 문자열의 위치) 인 새 그래프를 작성할 수도 있습니다. 엡실론 전환이라면 각 위치에 대한 상태와 다른 상태 사이에 엣지가 있습니다. 또한 s->s' 전환 문자가 문자열의 위치 pos에있는 문자와 일치하면 (s, pos) -> (s', pos + 1) 모서리가 있습니다.
그래프를 작성한 후에 적어도 하나의 터미널 상태 t에 대해 (t, string.length()) 쌍이 도달 할 수 있는지 확인해야합니다 (모든 그래프 탐색 알고리즘을 사용하여 깊이 우선 검색과 같은 방법으로 확인할 수 있습니다).

출처

2017-04-16 22:26:10 kraskevich

라인이 NFA와 일치하는지 어떻게 확인할 수 있습니까?

답변

관련 문제