1
나는 모든 NFA가 하나의 최종 상태로 변환 될 수 있음을 증명하려고 노력하고 있지만, 최종 상태가 0 인 경우를 어떻게 다루어야하는지 잘 모르겠습니다.NFA에는 필연적으로 최종 상태가 있습니까?
A
답변
1
모든 일반적 정의에 따라 다르지만 :
이- 수용 상태의 세트는
- 모든 상태는 초기 상태에서
모든 NFA 연결할 수 있어야 비어있을 수 있습니다 적용하지 않고 상태는 다음 두 가지 상태를 갖는 DFA와 거의 같습니다. 모든 입력에서 자체로 루프되는 초기, 비 승인 상태. 모든 입력에서 자체적으로 반복되는 도달 할 수없는 수용 상태가 있습니다.
공식적인 정의 (위키 백과에서 나는 내 책을 꺼내는 기분이 들지 않습니다)는 최종 상태 세트가 비어있을 수 있다고 제안하는 것 같습니다. 따라서 연결이 끊긴 NFA (즉, 최종 상태가 연결 해제 된 상태)가 아니면 NFA로 변환 할 수있는 것처럼 보이지 않습니다. 어쨌든, 나는이 질문이 여기에있는 것처럼 당신이 "마지막 상태가> 0 인 모든 NFA들"을 지정할 수 있다고 생각할 것이다 : http://cs.stackexchange.com/q/14555/29703. 그 메모에서 cs.stackexchange는 아마도이 질문에 더 좋은 곳일 것입니다. –
빈 세트는 다른 모든 세트의 서브 세트이기 때문에 제 책에는 최종 상태가 필요하다는 것을 나타내는 내용도 없습니다. –