허용 언어 및 결정 언어

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

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

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

튜링 머신 설계

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

예 1

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

Solution

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

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

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

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

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

그 후,

M = {{q 1 , q 2 }, {1}, {1, B}, δ, q 1 , B, {q 2 }}

여기서 δ는 −

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

예 2

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

Solution

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

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

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

  • 만약 Mq0, 0을 읽으면 오른쪽으로 이동하여 상태로 들어갑니다. q1 0을 지 웁니다. 1을 읽으면 상태가됩니다. q2 오른쪽으로 이동합니다.

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

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

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

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

그 후,

M = {{q 0 , q 1 , q 2 , q 3 , q 4 , q f }, {0,1, B}, {1, B}, δ, q 0 , 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