왜이 경우 유한 상태 기계를 구성 할 수 없습니까?

enter image description here

{0,1}에서 정확하게 그 서열을 인식하는 유한 상태 기계를 구성 할 수 없습니다 ..

난 단지 돈 왜 이런 일이 가능하지 않은지 모르겠다. 어쩌면 나는이 새로운 것을 보지 않을 것이다.

2014-11-18 lolwuwunoo

주제가 있나요? – mjs

이 사이트는 프로그래밍 관련 질문입니다. CS 이론이 아닙니다. 시도해보십시오. cs.stackexchange.com – Jubobs

게시 한 언어가 정규 언어가 아니며 일반 언어 (정규 문법으로 정의) 만 유한 상태 시스템에서 허용 할 수 있습니다.

이 이유는 비공식적으로 유한 자동 상태가 유한 상태 수를 가지므로 계산할 수 없기 때문입니다. 이것은 당신의 예제에서 i와 j를 비교하는 데 필요할 것입니다.

귀하의 언어가 contextfree이기 때문에 귀하의 언어를 수락 할 수있는 구조가 스택 자동 모드가됩니다. 자세한 내용은 chompsky 계층 구조 1에 대한 위키 백과 문서를 참조하십시오.

2014-11-18 08:10:25 Horstinator

유한 오토 마톤 *은 계산할 수 있지만 고정 정수로만 계산할 수 있습니다. 예를 들어, 짝수 개의 'a'와 짝수 개의 'b'가 포함 된 문자열을 캡처하는 유한 오토 마톤을 구축 할 수 있습니다. 그러한 오토 마톤은 효과적으로 모듈로 2를 계산합니다. – Jubobs

물론 당신은 정확합니다. 언급 된 언어에서 요구하는 것처럼 나는 무한한 계산을 언급했습니다. – Horstinator

답변