나는 당신이 찾고있는 “왜”의 맛을 잘 모르겠습니다. 비결 정성을 허용 할 때 전력이 증가하는 한 가지 이유는 다음 예에서 볼 수 있습니다.

하자 회문들의 집합 일부 알파벳 (적어도 두 개의 심볼) 이상, 의 역이다 . 이 언어의 NPDA는 기호를 스택에 계속 밀어 넣은 다음 입력의 중간에 도달하여 점진적으로 스택을 비 웁니다. 수용 조건은 순전히 존재한다는 점에 유의하십시오. 단어를 받아 들일 수있는 정확한 추측이 있으면 충분합니다.L

$L$

$L$ww¯

$w\overline{w}$

$w\bar{w}$w¯

$\overline{w}$

$\bar{w}$w

$w$

$w$

결정 론적 PDA는 현재 접두사에만 의존하는 방식으로 중간을 고려하는 위치를 선택해야합니다. 가 그러한 DPDA라고 가정하십시오 . 임의의 경우 ,하자 ; 하자 비어있는 단어, 그리고 . 이는 그래서, 회문 시퀀스 다음 각 접두사 받아들이는 상태에 있어야 스택 읽은 후, 공창, . 비둘기 구멍 원리에 의해 및 과 같은 이 있어야합니다.A

$A$

$A$k∈N

$k\in \mathbb{N}$

$k\in\mathbb{N}$uk=ab2ka

$u_k=a{b}^{2k}a$

$u_k=ab^{2k}a$v0

$v_0$

$v_0$vk+1=vkukvk

$v_{k+1}=v_k{u}_k{v}_k$

$v_{k+1} = v_ku_kv_k$A

$A$

$A$qk

$q_k$

$q_k$vk

$v_k$

$v_k$k,l

$k,l$

$k,l$k≠l

$k\ne l$

$k\neq l$qk=ql

$q_k=q_l$

$q_k=q_l$(유한 한 수의 상태가 있으므로 무한 수의 가 있으므로 일부는 ‘재사용’해야합니다 ). 그러나 구별 할 수 에서, 회문 인 하지 않습니다.k

$k$

$k$A

$A$

$A$vkukvk

$v_k{u}_k{v}_k$

$v_ku_kv_k$vlukvk

$v_l{u}_k{v}_k$

$v_lu_kv_k$

---

답변