튜링 머신에 DPDA?

Question

결정적 푸시 다운 오토 마톤을 튜링 기계로 변환 할 수있는 방법이 있습니까? 테이프에 입력 한 후 스택에 넣을 생각, 그 사이에 '#'. 그러나 그것을 형식적으로 증명하는 것은 불가능한 것처럼 보입니다.

의견이 있으십니까? 누군가 이미 그것을 했습니까?

감사합니다.

Answer 1

푸시 다운 자동 장치는 한 방향으로 만 작동합니다. 그것은 그것의 발걸음을 되돌아 가거나 카운트를 유지할 수 없다는 것입니다. 예를 들어
, 당신은 공식 언어하려면 다음은 어떤

L = {1^n+0^m | n>m, m>0} 

합니다. 1의 값이 no보다 큽니다. 0의.
이 문제는 DPDA 및 튜링 기계 모두에서 해결할 수 있습니다.

우리가 같은 다른 조건을 추가, 그러나 경우 :

L = {1^n.0^m.1^n | n>m, m>0} 

당신이 튜링 기계 위의 문제를 해결하는 방법을 알고 있다고 가정하면, 입력 테이프를 추적 다시하지 않고 그것을 해결하기 위해 할 수 없습니다 이해할 것이다.
따라서 튜링 머신만큼 강력한 PDA를 만들 수있는 방법은 없습니다. 여기
이 더 이해 위키 링크입니다 : 할`STACK-기호 # 입력 STRING`는 입력 심볼의 경우도 왼쪽에서 왼쪽 기호를 읽기 읽기 https://en.wikipedia.org/wiki/Chomsky_hierarchy 입력 테이프에