DFA와 루프, NFA 및 재귀 사이에 관계가 있습니까?

Question

DFA를 루프로 시뮬레이션 할 수 있고 NFA를 재귀 적 방법으로 시뮬레이션 할 수 있다고 들었습니다. 나는 그것이 어떻게 작동하는지 이해하지 못한다. 아무도 내게 모범을 줄 수 있습니까?

Answer 1

의미에서. DFA는 switch 구문을 사용하여 do...while 루프를 작성하여 현재 상태를 기반으로 쉽게 시뮬레이션 할 수 있지만 NFAs 용 시뮬레이터는 트리에서 검색을 수행 할 때 생각할 수 있지만 (깊이 첫 번째 검색은 재귀 적입니다. 넓이 우선 검색을 상상해보십시오). 여기에는 실제 형식이 전혀 없으며 시뮬레이터 구현 방법에 대한 일반적인 관찰 만 있습니다.