변환 RE> NFA

Question

나는 비 결정적 유한 상태 오토마타에 정규 표현식의 변환에 관한 질문이 있습니다.

암 I을 완전히 빗나 다음과 같이 나의 시도는 무엇입니까? 아니면 거기에?

NB의 E => ε

Answer 1

귀하의 NFA가 (a*|b*)*와 같은 언어와 일치하는, 그래서 대답은 올바른 것입니다.

그러나 동일한 언어와 일치하는 많은 NFA가 있으며, 귀하의 경우 최소한 3 개의 엡실론 화살표를 제거 할 수 있습니다. 그래도 귀하의 제안보다 정확하지는 않습니다.

정규식 (a*|b*)*도 의미를 변경하지 않고 간단하게 할 수 있습니다. 예 : (a|b)*은 (a*|b*)*과 같습니다. 생각해 보면 FA는 다음과 같이 간단 할 수 있습니다.