1
특정 언어의 DFA는 모든 DFA의 하위 집합이므로 DFA는 계산 가능하다는 것을 알고 있습니다. DFA의 수가 특정 언어를 받아들이는 것이 무한하다는 것을 증명하는 방법에 대해서 궁금해하십니까?동일한 언어를 사용할 수있는 DFA의 수는 무한대입니다
A
답변
2
해당 언어로 된 DFA를 가져옵니다. 다른 사이클/루프를 포함해야합니다. 사이클에 해당하는 새로운 상태 집합을 추가하고이 상태 집합이 사이클/루프를 통해 홀수 번호의 패스를 나타내는 것을 허용합니다 (원래 상태는 짝수 패스를 나타냄). 필요한 경우 비 결정론을 추가하고 powerset 구성을 사용하여 NFA를 다시 DFA로 만듭니다.
어느 쪽이든 상태가 더 많은 동일한 언어에 대한 DFA로 끝납니다.
모든 DFA는 유한 상태 수를 갖기 때문에주기가 있어야하지만 입력 문자열에있는 많은 전환을 가져야하므로 임의로 커질 수 있습니다. DFA는 충돌이 허용되지 않습니다. n 개의 상태가있는 DFA는 길이가 n + 1 인 문자열을 처리 (수락 또는 거부) 할 수 있어야합니다. 즉, 어떤 상태가 두 번 방문 했으므로 루프가 있음을 의미합니다. 다시 말하지만, 모든 DFA에는 루프/사이클이 있습니다. "반례 샘플"을 제공하면 루프 /주기가 있거나 DFA가 아닌 것으로 표시됩니다. – Patrick87
감사합니다. 도움이됩니다. –
상태 머신에 모두 도달 할 수있는 N 개의 상태가 있고 k 기호의 알파벳에서 입력을 받아들이지 만 기계에 대해 아무것도 알지 못한다면 가장 짧은 입력을 계산할 수있는 방법이 있습니까? 모든 N * k 상태 전이가 보장됩니다 (즉, 조건을 충족하는 모든 상태 머신의 모든 상태 전이가 발생합니다). – supercat