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

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

$$[\mbox{tape to the left}][\mbox{head}][\mbox{tape to the right}]$$

여기:

• [tape to the left]
  $[\text{tape to the left}]$

  $[\mbox{tape to the left}]$신청 후 P

  $P$

  $P$문자 만 포함 0¯¯¯

  $\overline{0}$

  $\overline0$ 과 1¯¯¯

  $\overline{1}$

  $\overline1$.

• [tape to the right]
  $[\text{tape to the right}]$

  $[\mbox{tape to the right}]$신청 후 P

  $P$

  $P$문자 만 포함 0

  $0$

  $0$ 과 1

  $1$

  $1$.

• [head]
  $[\text{head}]$

  $[\mbox{head}]$ 단일 비 터미널이며 헤드 상태와 헤드 위치의 문자를 모두 인코딩합니다.

머리가 상태라고 가정 S

$S$

$S$머리 아래 문자는 i∈{0,1}

$i\in \{0,1\}$

$i\in\{0,1\}$. 그런 다음 머리는 비 터미널로 표현됩니다.Si

$S_i$

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

$T$

$T$현재 문자를 j

$j$

$j$왼쪽으로 이동하면 두 가지 전환이 있습니다. Si→0T0j

$S_i\to 0T_{0}j$

$S_i\rightarrow0T_0j$ 과 Si→1T1j

$S_i\to 1T_{1}j$

$S_i\rightarrow1T_1j$. 대신 오른쪽으로 이동해야하는 경우 두 가지 전환이 있습니다.Si→j¯T00¯¯¯

$S_i\to \overline{j}{T}_0\overline{0}$

$S_i\rightarrow\overline jT_0\overline0$ 과 Si→j¯T11¯¯¯

$S_i\to \overline{j}{T}_1\overline{1}$

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

$[\text{tape to the left}]$

$[\mbox{tape to the left}]$ 또는 [tape to the right]

$[\text{tape to the right}]$

$[\mbox{tape to the right}]$ 위반 될 것이며 결코 회복되지 않을 것입니다.

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

---

답변