Non-Finite Automata to Deterministic Finite Automata

두비니

·

2021. 4. 16. 19:18

 

 


Non-Finite Automata to Deterministic Finite Automata

NFA를 DFA로 바꾸기


 

 

수학은 왜이렇게 변환하는걸 좋아할까요?

아무튼 NFA를 DFA로 바꾸는 방법, 그리고 검산하는 방법을 맨날 까먹어서 글로 작성합니다.

누군가에게도 도움이 되길

 

 

일단 NFA와 DFA의 가장 큰 차이점은 DFA가 규제가 훨씬 더 많다는 것입니다. 따라서 NFA를 DFA로 바꾸기 위해서는 조건에 맞춰서 DFA로 모두 바꿔주면 됩니다.

 

그 전에 별 의미없는 증명을 먼저 합시다.

 

Theorem : Every NFA has an equivalent DFA.

 

 

그냥 외우는 편이 좋을 듯 합니다.

어떤 임의의 NFA로 이런방식으로 DFA를 만들었더니, 와! 똑같잖아!의 맥락이라..

 

 

NFA To DFA

 

바꾸는것도 그냥 그대로 따라서 바꾸면 됩니다.

 

(작성중)