허용 언어 및 결정 언어

TM은 입력 문자열 w에 대해 최종 상태가되면 언어를 허용합니다. 언어가 Turing 머신에서 허용되는 경우 재귀 적으로 열거 할 수 있습니다 (Type-0 문법에 의해 생성됨).

TM은 언어를 받아들이면 언어를 결정하고 해당 언어가 아닌 입력에 대해 거부 상태가됩니다. 언어는 Turing 머신에 의해 결정되면 재귀 적입니다.

TM이 멈추지 않는 경우가있을 수 있습니다. 그러한 TM은 언어를 받아들이지 만 결정하지는 않습니다.

튜링 머신 설계

튜링 머신 설계의 기본 지침은 몇 가지 예를 통해 아래에 설명되어 있습니다.

예 1

홀수의 α로 구성된 모든 문자열을 인식하도록 TM을 설계합니다.

Solution

튜링 머신 M 다음과 같은 이동으로 건설 할 수 있습니다.

• 허락하다 q₁ 초기 상태입니다.

• 만약 M 에 q₁; α를 스캔하면 상태로 들어갑니다.q₂ 그리고 쓴다 B (공백).

• 만약 M 에 q₂; α를 스캔하면 상태로 들어갑니다.q₁ 그리고 쓴다 B (공백).

• 위의 움직임에서 우리는 M 주에 들어가다 q₁ 짝수 개의 α를 스캔하여 상태가되면 q₂홀수의 α를 스캔하는 경우. 그 후q₂ 유일한 수용 상태입니다.

그 후,

M = {{q ₁ , q ₂ }, {1}, {1, B}, δ, q ₁ , B, {q ₂ }}

여기서 δ는 −

테이프 알파벳 기호	현재 상태 'q 1 '	현재 상태 'q 2 '
α	BRq 2	BRq 1

예 2

이진수를 나타내는 문자열을 읽고 문자열의 모든 선행 0을 지우는 Turing Machine을 설계합니다. 그러나 문자열이 0으로 만 구성된 경우 하나의 0을 유지합니다.

Solution

입력 문자열이 문자열의 각 끝에있는 공백 기호 B로 종료된다고 가정하겠습니다.

튜링 머신, M, 다음 이동에 의해 건설 될 수 있습니다-

• 허락하다 q₀ 초기 상태입니다.

• 만약 M 에 q₀, 0을 읽으면 오른쪽으로 이동하여 상태로 들어갑니다. q₁ 0을 지 웁니다. 1을 읽으면 상태가됩니다. q₂ 오른쪽으로 이동합니다.

• 만약 M 에 q₁, 0을 읽을 때 오른쪽으로 이동하고 0을 지 웁니다. 즉, 0을 B로 대체합니다. 맨 왼쪽 1에 도달하면q₂오른쪽으로 이동합니다. B에 도달하면 즉, 문자열이 0으로 만 구성되어 있으면 왼쪽으로 이동하여 상태로 들어갑니다.q₃.

• 만약 M 에 q₂, 0 또는 1을 읽으면 오른쪽으로 이동합니다. B에 도달하면 왼쪽으로 이동하여 상태로 들어갑니다.q₄. 이것은 문자열이 0과 1로만 구성되어 있는지 확인합니다.

• 만약 M 에 q₃, B를 0으로 대체하고 왼쪽으로 이동하여 최종 상태에 도달합니다. q_f.

• 만약 M 에 q₄, 0 또는 1을 읽으면 왼쪽으로 이동합니다. 문자열의 시작 부분에 도달하면 즉, B를 읽으면 최종 상태에 도달합니다.q_f.

그 후,

M = {{q ₀ , q ₁ , q ₂ , q ₃ , q ₄ , q _f }, {0,1, B}, {1, B}, δ, q ₀ , B, {q _f }}

여기서 δ는 −

테이프 알파벳 기호	현재 상태 'q 0 '	현재 상태 'q 1 '	현재 상태 'q 2 '	현재 상태 'q 3 '	현재 상태 'q 4 '
0	BRq 1	BRq 1	ORq 2	-	OLq 4
1	1Rq 2	1Rq 2	1Rq 2	-	1Lq 4
비	BRq 1	BLq 3	BLq 4	OLq f	BRq f