8
렉서에 DFA 최소화기를 구현하려고하지만 해당 DFA가 이미 최소 DFA 인 것처럼 보이지 않는 DFA를 생성 할 수 없습니다. 표현.유효하지 않은 상태 또는 불필요한 상태로 DFA를 생성하는 정규식
나는 후미 정규 표현식에서 톰슨 구조를 사용하여 작성된 NFA에서 DFA를 구성하고 있습니다. 용 책에 묘사 된 내용은 거의 정확히 그대로입니다. 렉서를 만들려면 NFA의 몇 개가 시작 상태에서 엡실론 전환을 사용하여 결합됩니다. 이 결합 된 NFA에서 DFA 알고리즘이 적용됩니다.
그래서 죽은 상태 제거 및 상태 최소화를위한 멋진 테스트 베드를 만드는 DFA를 생성하는 "알려진"정규 표현식이 있습니까?
물론 이상한 DFA를 해킹하고 알고리즘을 적용 할 수는 있지만 실제로 적절한 테스트 케이스는 아니겠습니까? DFA를 구성하는 메소드가 죽은 상태가 발생하지 않도록하려면 해당 정보도 가치가있을 것입니다. 그 이후로 상태 제거 기능을 모두 구현하지 않아도됩니다.
편집 : 정확하게 대답하기 위해 구현 세부 사항을 필요로 경우, 코드가, 특히 NFA.cs 및 DFA.cs 클래스 github 볼 수 있습니다. 또한 내가 도움이된다면, 내가 사용하고있는 건설 알고리즘에 대한 blog posts에 관한 시리즈를 썼다.