1
1의 짝수와 0으로 끝나는 결정 집합 유한 오토마타를 생성해야합니다.이 집합에서 0을 문자열로 포함할까요? 어떻게해야합니까?어떻게 유한 오토마타를 구성 할 수 있습니까
A
답변
2
이 세트의 문자열로
0을 포함해야합니까?
예 그리고 이걸 어떻게해야합니까?
유한 오토 마톤을 구성하려면 상태와 전환을 식별해야합니다. Myhill-Nerode 정리를 사용하면 "구별 할 수없는"문자열의 등가 클래스를 식별 할 수있는 경우 유한 오토 마톤에 필요한 (그리고 충분한!) 상태를 찾을 수 있습니다.
두 문자열 x 및 y,이 점에서 구별 할 수없는 경우 다른 문자열 z에 대한 하나 xz 및 yz이도 아닌 언어로, 또는 둘 다.
귀하의 경우, 동등한 클래스를 확인해 보겠습니다. 빈 문자열은 일부 동등한 클래스에 있습니다. 0 문자열은 0에 빈 문자열을 추가하고 해당 언어로 문자열을 가져올 수 있으므로 (빈 문자열에 빈 문자열을 추가하여 언어로 문자열을 가져올 수는 없으므로) 다른 동급 클래스에 있습니다. 지금까지 두 개의 별개의 등가 클래스를 발견했습니다. 하나는 빈 문자열이고 다른 하나는 0입니다. 이 두 가지 모두 FA에서 다른 주를 필요로합니다.
문자열 1은 어떨까요? 0과 빈 문자열은 10을 1에 추가하여 110 문자열을 가져올 수 있지만 언어에 문자열을 가져 오려면 0 또는 빈 문자열에 추가 할 수 없으므로이 문자열을 빈 문자열과 구별 할 수 있습니다. 그래서 우리에게는 또 다른 국가가 있습니다.
문자열 00은 어떨까요? 이 문자열은 언어가 아니며이 문자열에 다른 문자열을 추가하여 언어로 문자열을 가져올 수 없습니다. 이것은 또 다른 등가 클래스입니다. 다음 문자열 인 01과 10도이 클래스에 속합니다.
문자열 11은 빈 문자열과 같은 클래스로 끝납니다. 언어의 문자열을 11에 추가하고 언어에서 다른 문자열을 얻을 수 있습니다. 길이가 3 인 문자열을 모두 시도하면 위의 클래스 중 하나에 해당하는 문자열이 모두 있다는 것을 알 수 있으며 그 시점에서 검사를 중지 할 수 있습니다.
우리는 4 가지 상태가 있습니다. [-], [0], [1] 및 [00]으로 전화를 걸도록하겠습니다. 이제 우리는 전환을 파악합니다. 당신이 [-]에서 0을받을 경우
, 당신은 [0]에 갈 필요가 ... 그리고 당신이 1를 얻을 경우, 당신은 [1]로 이동해야합니다. 나머지의 경우 표준 문자열에 추가하여 얻는 문자열과 결과 문자열이 어떤 클래스인지 파악하고 그 상태로 이동하십시오.