0
길이가 < = k 인 모든 문자열을 인식하고 길이가 k보다 큰 모든 문자열을 거부하는 k 상태로 NFA를 구성 할 수 있습니까?길이가 k 인 문자열을 허용하는 k 상태의 NFA
A
답변
0
No. 증명은 k에 수학적 유도에 의한 것입니다.
기본 사례 : k = 0의 경우 0 상태를 가진 NFA는 유효한 개체조차 존재하지 않을 것이므로 어떤 것도 허용한다고는 할 수 없습니다. 편집 : k = 0 케이스가 변칙이므로 k = 1도 추가할만한 가치가 있습니다. k = 1의 경우 상태가 수락되지 않는 경우 (수락 된 언어가 비어있는 경우) 또는 수락중인 경우 빈 문자열 (입력을 사용하는 전환이없는 경우) 또는 무한히 많은 문자열 (if 입력을 소비하는 전환이 있습니다).
유도 가설 : 및 n을 포함한 모든 k에 대한 가정, k 이하의 상태가 k보다는 더 이상 길이 문자열을 받아들이고 k보다 큰 길이 문자열을 거부 아무 NFA가 없습니다.
유도 단계 : k+1 또는 길이가 k+1 이하인 문자열을 허용하는 더 적은 상태의 NFA가없고 길이가 k+1보다 큰 문자열을 거부하는 것이 표시되어야합니다. 그런 NFA가 있었다고 가정하십시오. 이 NFA의 수락 상태를 고려하십시오. NFA가 많은 문자열과 빈 문자열 (k = 1에 대한 기본 경우 참조) 이상을 허용하기 때문에 초기 상태 이외의 적어도 하나가 있어야합니다. 또한 NFA에는 일부 다른 입력 상태에 도달 할 수있는 상태가 있어야합니다. 일부 입력은 해당 상태에 도달하기 위해 소비되어야하기 때문입니다. 하나의 입력 기호를 사용하여 이러한 다른 수락 상태에 도달 할 수있는 상태 세트를 고려하십시오. 수용하는 것으로 표시된 상태의 새로운 집합으로 대체 된 다른 수락 상태를 가진 새로운 NFA를 고려하십시오. 결과 NFA는 (k + 1 세트의 상태 집합에서 적어도 하나의 다른 수용 상태를 제거 했으므로) k 개 이하의 상태에서 길이가 k보다 크지 않은 모든 문자열을 수용합니다. 이것은 유도 가설과 모순되기 때문에, 길이가 k + 1보다 크지 않은 모든 스트링을 수용하는 k + 1 상태를 가진 NFA는 존재하지 않는다.
0
길이가 < k 인 경우에도 true입니다.
길이가 < = k이면 길이가 k 인 문자열 w를 고려하십시오. 그것은 어떤 길을 따라 받아 들여진다. 이 경로는 k + 1 개 주를 방문합니다. k 개의 뚜렷한 상태가 있으므로 적어도 하나는 두 번 방문됩니다. 경로에 루프가 있습니다. 이 루프는 여러 번 수행 할 수 있습니다. 따라서 무한히 많은 문자열이 받아 들여지며 특히 k보다 긴 문자열도 무의식적으로 허용 될 수 있습니다.
사례 k = 1 : 전환 없음은 빈 문자열 만 받아 들임을 의미합니다. 그렇지 않으면 모든 문자에 대해 루프가 있거나 없을 수 있으므로 몇 가지 다른 언어를 사용할 수 있습니다. 아니면 NFA가 완성되어야한다고 생각하십니까? –
유도 단계의 경우 첫 번째 문자가 다른 경우 다른 상태로 이어질 수 있습니다. 따라서 두 번째 상태는 k에 대한 오토 마톤의 시작 상태와 같을 필요는 없습니다. 문자열의 일부만 받아 들일 수 있고 나머지는 다른 두 번째 상태를 통해 받아 들여질 수 있습니다. –
@PeterLeupold 첫 번째 의견을 말씀 드리 자면, 당신이 옳았습니다. 작성된 내용을 살펴보면 당시 DFAs를 염두에두고 있다고 생각합니다. 두 번째로, 다른 주를 이끄는 다른 편지는 문제가되지 않지만 (나는 생각한다) 다른 주를 이끄는 동일한 편지는 당신이주는 이유로 문제가된다. 이 의견을 토대로 몇 가지 사항을 변경하고 그 해답이 충분히 개선 될 수 있는지 살펴 보겠습니다. – Patrick87