1의 짝수와 0으로 끝나는 결정 집합 유한 오토마타를 생성해야합니다.이 집합에서 0을 문자열로 포함할까요? 어떻게해야합니까?어떻게 유한 오토마타를 구성 할 수 있습니까
답변
이 세트의 문자열로
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]
로 이동해야합니다. 나머지의 경우 표준 문자열에 추가하여 얻는 문자열과 결과 문자열이 어떤 클래스인지 파악하고 그 상태로 이동하십시오.
- 1. 비 결정적 유한 오토마타를 구축하십시오
- 2. 정규 표현식에 해당하는 유한 상태 오토마타를 생성합니다. 내 해결책이 맞습니까?
- 3. 비 결정적 유한 변환기를 어떻게 시뮬레이트 할 수 있습니까?
- 4. nowjs를 어떻게 구성 할 수 있습니까?
- 5. asp.net mvc에서 어떻게 구성 할 수 있습니까?
- 6. gsoap : 어떻게 구성 할 수 있습니까?
- 7. 10 진수로도 유한 오토 마톤을 어떻게 만들 수 있습니까?
- 8. 유한 상태 기계를 이전 상태로 전환 할 수 있습니까?
- 9. MFMailComposeViewController를 구성 할 수 있습니까?
- 10. 유한 상태 오토마타의 특정 응용 프로그램은 무엇입니까?
- 11. JavaScript로 꾸준한 오토마타를 만들려면 어떻게해야합니까?
- 12. 작은 유한 집합의 가능한 값에 대해 어떻게 비정규 화/히스토그램 mysql 출력을 할 수 있습니까?
- 13. 어떻게 Gmail과 함께 작동하도록 Drupal 6을 구성 할 수 있습니까?
- 14. ASP.NET 프로젝트를 재사용을 위해 어떻게 구성 할 수 있습니까?
- 15. PhpEclipse에서 포맷터 설정을 어떻게 구성 할 수 있습니까?
- 16. 레일스 :/: id에 대해 routes.rb를 어떻게 구성 할 수 있습니까?
- 17. 어떻게 정리하고 뷰 (MVC)를보다 잘 구성 할 수 있습니까?
- 18. ASP.NET MVC 멤버십 : 어떻게 만들거나 구성 할 수 있습니까?
- 19. Android 갤러리 구성 요소는 어떻게 사용자 정의 할 수 있습니까?
- 20. 어떻게 Ext.NET Calendar Control을 구성 할 수 있습니까?
- 21. AS3 :이 연결 문제를 어떻게 구성 할 수 있습니까?
- 22. 어떻게 나의 자식 구성/후크를 propogate 할 수 있습니까?
- 23. 런타임에 구성원 개체를 구성 할 때 어떻게 변경할 수 있습니까?
- 24. 어떻게 어설 션 오류를 표시하도록 이클립스를 구성 할 수 있습니까?
- 25. AS3 :이 Array 문제를 어떻게 구성 할 수 있습니까?
- 26. CPAN이 C를 컴파일하지 못하면 어떻게 CCFLAGS를 구성 할 수 있습니까?
- 27. 어떻게 Perl CGI 스크립트를 실행하도록 Apache를 구성 할 수 있습니까?
- 28. 어떻게 PowerShell을 사용하여 SQL Server 2008을 구성 할 수 있습니까?
- 29. openssl의 기본 백엔드 엔진을 어떻게 구성 할 수 있습니까?
- 30. 어떻게 안드로이드에서 이러한 UI를 구성 할 수 있습니까?