정규 표현식이 주어졌으며 NFA와 DFA로 변환하고 싶습니다. 다음은 정규 표현식입니다.맞습니까? (Finite Automata)
a (b | c) * a | 여기 NFA http://img148.imageshack.us/img148/4237/nfa.png
와 DFA 것 : AAC의 * B 그리고
나는 톰슨의 알고리즘을 사용하여 NFA이를 coverted DFA http://img9.imageshack.us/img9/2476/dfae.png
누군가가 나에게 내가 알고하자에 잠깐 살펴 주실 래요 잘못되었거나 맞았습니까?
매우 숙제 일 가능성이 높으므로 완전한 해결책을 제공하는 것이 주저합니다.
귀하의 NFA는 정확하지만 필요한 불필요한 상태가 많지만 정확성에 나쁜 영향을 미치지 않습니다. (언뜻 보면 11 개 주를 제거 할 수있는 것처럼 보입니다.)
DFA가 올바르지 않습니다. 이것은 문자열의 한 조건 또는 다른 조건을 처리하기 위해 분기 할 때 나중에 함께 다시 결합하기 때문입니다. 이렇게하면 노드 15,17 또는 11으로 이동하여 a(b|c)*a과 일치하는 허용 된 문자열에서 경로를 가져 와서 b 또는 c을 가져올 수 있습니다. 그런 다음 표현식과 일치하지 않더라도이 문자열을 허용합니다.
당신이해야 할 일은 기본적으로 이런 일이 일어나지 않게하는 것입니다. 추가 질문이 있으시면 언제든지 물어보십시오.
오토마타가 올바른 (수락 또는 거부) 상태로 끝나는지 확인하고 받아 들여서는 안되는 테스트 문자열 목록을 작성한 다음 추적하는 것이 좋습니다.
방금 편집했는데이 말이 맞는지 말해 줄 수 있습니까? http://img263.imageshack.us/img263/7606/dfah.png 감사합니다! – user635064
+1이지만 불필요한 엡실론 전환은 비현실적이지 않습니다. 많은 오토 마타 툴킷은 많은 것을 생성합니다. –
'aa'는 지금 받아 들여지지 않습니다 만, (15.17 절의 루프에서'c'가 사라 졌다고) 생각합니다. 그리고 실제로 나는 그들이 비현실적이지 않다는 것을 알고 있습니다, 저는 항상 수동으로 automatas를 만들었습니다. 그런 식으로 무언가는 저를 바라 보는 것만 같습니다. –
DFA가 잘못되어 다른 잘못된 문자열 중에서 'abacb'을 허용합니다. 당신은 또한 당신의 NFA에서 불필요한 엡실론 전이를 많이 겪었지만 그다지 중요하지는 않습니다. 일반적으로 동등한 DFA는 거의 항상 NFA보다 더 많은 주를 갖습니다. –
또한 숙제라고 가정합니다. –
예, 숙제. 나는 해결책을 묻지 않고 있습니다. 나는 올바른 방향에 있는지 아닌지를 알고 싶습니다. 그리고 대답에 감사드립니다. – user635064