2
유한 오토 마톤보다 강력하지만 결정적 푸시 다운 오토 마톤보다 강력하지 않은 것이 있습니까?DFA보다 강력하지만 DPDA보다 작은
A
답변
4
확실히. 하나의 스택 심볼만을 사용하는 DPDA로 UDPDA를 정의하자. 즉, 스택 알파벳은 단항 문자이다. 그러한 기계는 언어 L = {a^n b^n | n> 0}, 그러나 언어 P = {w $ w^R | w는 간단한 문장의 임의의 문자열}입니다. 스택을 사용하지 않아도 일반 언어를 인식 할 수 있습니다. 따라서 L (DFA)은 L (UDPDA)의 하위 집합이며 L (DPDA)의 하위 집합입니다.
많은 다른 종류의 오토마타를 정의 할 수 있습니다. 이보다 훨씬 더 이색적이고 법안에 적합 할 수 있습니다. 예를 들어, 푸시 다운 오토 마트보다 강력하거나 강력하지 않은 최소 힙 오토마타를 정의했습니다. cs.stackexchange.com 또는 Google "min heap automata"를 검색하면 해당 항목에 대해 알 수 있습니다.
+0
감사합니다. 제안 된 지침을 더 자세히 살펴 보겠습니다. –
프로그래밍 문제입니까? 두문자어의 일부를 제거하고 도메인을 식별하는 태그를 추가 할 수 있습니까? – Gray
cs.stackexchange.com에서이 질문을 할 수 있습니다. 더 나은 대답을 얻을 수 있습니다. – Patrick87