NFA DFA와 Regex to Transition Table

정규 표현식이나 문자열을 입력하고 NFA와 DFA로 변환하는 알고리즘을 찾고 있습니다. 실제로는 다음과 같은 전환 테이블을 인쇄합니다. 해당 최종 DFANFA DFA와 Regex to Transition Table

나는 이미 알고리즘이나 C 또는 파이썬 라이브러리가 있는지 궁금해하고 있습니다. 사용하려는 알고리즘에 대한 제안이 있다면 구현할 수 있습니다.

감사합니다.

2013-10-20 Anoracx

작성된 것처럼 귀하의 질문은 너무 광범위하여/주관적이어서 대답을하지 않아도됩니다. 직접 코딩해야하는지 또는 기존 라이브러리가 있는지 여부를 묻는 것입니다. Stack Overflow에서 이러한 양식에 대한 질문이 실제로 적절하지 않습니다. "이 문제를 해결하기 위해 어떻게 라이브러리 X를 사용합니까?"와 같이 좀 더 구체적으로 질문을 업데이트 할 수 있습니까? 또는 "여기에 가장 적합한 알고리즘은 무엇입니까?" – templatetypedef

글쎄, 기존 라이브러리가 있는지, 처음부터 if를 구현해야하는지 (또는 톰슨을 언급 한 이유) 누군가에게 내가 구현할 수있는 알고리즘을 알고 있다면 묻고 있었다. 그러나 나는 약간의 질문을 수정했다, 나는 그것이 더 분명하기를 바란다. – Anoracx

http://projectsgeek.com/2011/05/regular-expression-to-dfa-code-in-c-language.html –

이러한 링크 중 하나라도 도움이 될지 확실하지 않습니다.

첫 번째는 NFA에서 DFA 로의 변환과 함께 Python에서 매우 간단한 NFA/DFA 구현을 제공합니다. 그것은 정규식에서 NFA를 생성하지는 않지만 그렇게하는 것은 어렵지 않습니다. 두 번째 사이트는 수많은 코드 예제 (대부분 C 언어)와 내가 아는 외부 라이브러리에 대한 링크를 포함하여 NFA 대 DFA에 대한 긴 토론을 제공합니다. 세 번째와 네 번째 링크는 정규 표현식에서 NFA로 구문 분석 한 다음 NFA에서 DFA로 변환하는 것을 포함하여 두 번째 기사 작성자가 개발 한 두 개의 regex 엔진 구현 소스 코드를 제공합니다. 그러나 나는이 프로젝트들 중 하나를 보지 못했다.

그렇지 않으면, 나는 대부분의 실제 정규식 엔진이 때문에 일부 확장 기능, NFA,하지 DFA를 사용하는 것이 언급 것이라고 간단하게 할 수있는 DFA로 수행 할 수 없습니다. 따라서 위의 hte 링크 중 아무 것도 도움이되지 않는다면 DFAs를 실제로 사용하는 컴파일러 컴파일러를 보면서 행운을 볼 수 있습니다.

출처

2013-10-24 21:47:17 jwatkins

도움을 요청했지만 불행히도 링크를 살펴본 결과 해당 최종 DFA의 상태 테이블을 인쇄하는 알고리즘을 찾을 수 없었습니다. – Anoracx

그들은 전이 테이블을 아직 _print_하지 않았지만 최종 계산 된 DFA에서 추출하는 것은 간단합니다 ... 필요한 것은 각 노드를 거쳐 고유 한 순차 식별자를 할당하는 것입니다. 그런 다음 그래프를 다시 한 번 살펴보고 해당 노드 id, 각 전환에 대한 후속 노드의 ID로 가능한 전환 목록을 출력하십시오. 검사 할 수있는 구조로 DFA를 계산하는 것은 실제로 더 어려운 부분입니다. – jwatkins

답변

관련 문제