decidability Archives

알파벳 대한 임의의 문맥이없는 문법 를 고려하십시오 . 이 문법의 제작에 두 개의 고정 된 문맥에 맞지 않는 제작 : 및 . 결과 문법 를 ” 제작 보완 된 “를 나타냅니다. $G$

${0, 1, \bar{0}, \bar{1}}$

{0,1,0¯,1¯}

$P$

$\bar{0} 0 \to ϵ$

0¯0→ϵ

$\bar{1} 1 \to ϵ$

1¯1→ϵ

$G^{P}$

$G$

$P$

이것은 문법 얻어 알고리즘 수득 가능 , 문자열은 위에 및 결정 여부 ? $G^{P}$

$s$

${0, 1, \bar{0}, \bar{1}}$

{0,1,0¯,1¯}

$s \in L (G^{P})$

s∈L(GP)

이 문법 클래스는 결정할 수 없습니다. 튜링 머신을 에뮬레이트하는 데 사용하는 방법에 대한 대략적인 아이디어가 있습니다.

각 시점에서 현재 부분적으로 확장 된 단어는 다음과 같습니다.

[tape to the left] [head] [tape to the right]

여기:

머리가 상태라고 가정 $S$

머리 아래 문자는 $i \in {0, 1}$

i∈{0,1}

. 그런 다음 머리는 비 터미널로 표현됩니다. $S_{i}$

. 상태로 전환해야하는 경우 $T$

현재 문자를 $j$

왼쪽으로 이동하면 두 가지 전환이 있습니다. $S_{i} \to 0 T_{0} j$

Si→0T0j

과 $S_{i} \to 1 T_{1} j$

Si→1T1j

. 대신 오른쪽으로 이동해야하는 경우 두 가지 전환이 있습니다. $S_{i} \to \bar{j} T_{0} \bar{0}$

Si→j¯T00¯

과 $S_{i} \to \bar{j} T_{1} \bar{1}$

Si→j¯T11¯

. 어떤 의미에서, 머리는 일치하는 캐릭터를 생성함으로써 캐릭터가 움직이는 방향으로 캐릭터를 “추측”해야한다. 추측이 틀리면 $[tape to the left]$

[tape to the left]

또는 $[tape to the right]$

[tape to the right]

위반 될 것이며 결코 회복되지 않을 것입니다.

기계가 정지하면 헤드는 “추측”하여 일치하는 문자를 생성하여 테이프를 양쪽에서 “소비”해야합니다. 그 후, 그것은 빈 단어를 생산해야합니다. 결과적으로 빈 단어는 해당 Turing 기계가 정지 한 경우에만 해당 문법의 구성원이됩니다.

How IT