결정 성 질문

Question

실제 숫자를 결정하는 NFA가있을 수 있습니까?

Answer 1

아니요.

실수는 소수점 이하 무한 자릿수를 가질 수 있습니다. 이 숫자에는 시스템이 없을 수 있습니다 (즉, 임의의 프로세스에 의해 생성 될 수 있음). 이 경우 시퀀스 자체보다 훨씬 짧은이 자릿수 시퀀스에 대한 설명이있을 수 없습니다.

이제 실제 숫자 을 가져 오십시오. 어떤 NFA도 한정된 수의 상태만을 가지고 있고 유한하게 기술 될 수 있기 때문에 의 만 받아들이는 것은 부적절 할 것입니다. 그렇지 않으면 r의 유한 한 설명이 될 수 없다는 사실에 반하는 것입니다).

Answer 2

아니요, 없습니다. 비 결정적인 유한 오토 마톤은 문자열을 입력으로 받아들입니다. 모든 문자열의 집합은 유효하며 따라서 실수 집합보다 작습니다. 따라서 임의의 실수를 NFA의 입력으로 인코딩 할 수도 없습니다.