(ab u aab u aba) *을 NFA로 변환하는 방법?

Question

(AB 유 AAB U ABA) *

나는 그것을했지만 나는 그것의 정확성에 대한 몇 가지 의견을 싶습니다 정확하면

을 : 우리는 (AB U AAB U ABA) * 하나를 단순화 할 수 있습니다 더욱이?

만약 그렇지 않다면 무엇을 놓쳤습니까?

EDIT : 3 개의 모든 최종 상태에서 초기 상태로 전자 전환이 누락 된 것으로 보입니다. 전자 전환의 초기 상태로 이동하는 초기 상태와 최종 상태가 필요합니다. (Kleene Star 규칙).

P.S. (a u b)*aabab 및 (a u b)*a(a u b)(a u b)(a u b)(a u b)을 단순화 할 수 있습니까?

당신이로 쓸 수 있다는 점에서 첫 번째 케이스의 작은 단순화를 볼 수 있습니다 최소화/단순화 할 수있는 방법이 없다면, 그것은 터무니없이 긴 DFA되기 때문에 물어 이유는 ...

Answer 1

(a (bu ab u ba)) *하지만 반드시 도움이되지는 않습니다. 나는 여전히 귀하의 DFA가 귀하가 생각하는만큼의 주를 필요로하지 않을 것이라고 생각합니다.

두 경우 모두 읽은 마지막 5 문자를 추적하기 위해 32 개 상태의 DFA가 필요합니다. 차이점은 두 번째 DFA에는 터미널 상태가 하나만 있고 세 번째 DFA에는 16이 있다는 점입니다.