튜링 머신 - 튜링 기계는 유형 0 문법에 의해 생성된 언어의 단어를 받아들이는 데 사용되는 장치입니다. Turing Machine(TM)은 입력이 제공되는 셀로 분할된 무한 길이 테이프로 구성된 수학적 모델입니다. 입력 테이프를 읽는 헤드로 구성되어 있습니다. 상태 레지스터는 튜링 머신의 상태를 저장합니다. 입력된 기호를 읽은 후 다른 기호로 교체되고 내부 상태가 변경되어 한 셀에서 오른쪽 또는 왼쪽으로 이동합니다. TM이 최종 상태에 도달하면 입력 문자열이 수락되고 그렇지 않으면 거부됩니다.
TM은 공식적으로 7-튜플(Q, X, Σ, δ, q0, B, F)로 설명될 수 있습니다. 여기서 -
- Q는 유한한 상태 집합입니다.
- X는 테이프 알파벳입니다.
- Σ는 입력 알파벳입니다.
- δ는 전이 함수입니다. δ :Q × X → Q × X × {Left_shift, Right_shift}.
- q0은 초기 상태입니다.
- B는 공백 기호입니다.
- F는 최종 상태의 집합입니다.
우리의 목표는 언어를 수용하는 Turing machine TM을 구축하는 것입니다.
L=anbma(n+m) 여기서 n,m>=1
TM이 받아들일 수 있는 단어의 예를 들어보겠습니다.
- 아바, n=1,m=1
- 아아아아아, n=2,m=1
- 아바아아, n=1,m=2
- 아아아아아아, n=3,m=1
그것은 n 곱하기 a 다음에 m 곱하기 b 다음에 다시 n+m 곱하기 a입니다. n,m>=1
최소한 아니요. a의 a는 항상 3이고 b는 1입니다. 둘 다 n=m=1일 때
접근 방식은 아래에 요약되어 있습니다 -
기계는 먼저 모든 n 번호를 수락합니다. 의 뒤에 모두 m 번호가 옵니다. b의. 그런 다음 더 많이 만나면 이전 입력 b와 a를 삭제하기 시작합니다. 결국 새로운 문자가 오지 않고 머리가 첫 번째 입력 문자에 도달하면 모든 문자가 올바르게 처리되었음을 의미합니다. 입력 문자열에 대해 단계별로 따라가 보겠습니다 −
상태 q0에서 전환
-
δ (q0, a) → (q1, x, R). 상태 q0에서 문자 읽기가 상태 q1로 전환되면 x로 만들고 문자열의 다음 문자를 가리키도록 오른쪽으로 이동합니다.
Ex − aabaaa → xabaaa ( 첫 번째 문자가 x 머리가 다음 a 로 오른쪽으로 이동됨 )
-
δ ( q0, b ) → ( q3, x, R ). 상태 q0에서 문자 읽기가 상태 q3으로 전환되면 x하고 문자열의 다음 문자를 가리키도록 오른쪽으로 이동합니다.
예 - 바바아.... → 꺄아아.... (첫 번째 문자는 x 머리가 다음 a로 오른쪽으로 이동됨)
여기서 x는 첫 번째 문자를 나타내는 데 사용됩니다.
상태 q1에서 전환
-
δ ( q1, a ) → ( q1, a, R ). 상태 q1에서 문자 읽기가 a이면 상태 q1을 유지하고 오른쪽으로 이동하여 문자열의 다음 문자를 가리킵니다.
예:xaabaaa… → xaabaaa… (쉬는 동안 아무것도 하지 않고 오른쪽으로 이동)
-
δ ( q1, b ) → ( q2, b, R ). 상태 q1에서 문자 읽기가 b이면 상태 q1을 유지하고 문자열의 다음 문자를 가리키도록 오른쪽으로 이동합니다.
Ex − xaabaaa… → xaabaaa… (휴식 b의 경우 아무것도 하지 않고 오른쪽으로 이동)
상태 q2에서 전환
-
δ ( q2, b ) → ( q2, b, R ). 상태 q2에서 문자 읽기가 b이면 상태 q2를 유지하고 문자열의 다음 문자를 가리키도록 오른쪽으로 이동합니다.
Ex − xaabbbbaaa… → xaabbbbaaa… (나머지 b는 아무것도 하지 않고 오른쪽으로 이동)
-
δ ( q2, z ) → ( q2, z, R ). 상태 q2에서 문자 읽기가 z이면 상태 q2를 유지하고 문자열의 다음 문자를 가리키도록 오른쪽으로 이동합니다.
Ex − xaabaazz… → xaabaazz…
-
δ ( q2, a ) → ( q3, z, L ). 상태 q2에서 문자 읽기가 a이면 z로 만든 다음 상태 q3으로 이동하고 왼쪽으로 이동하여 문자열의 이전 문자를 가리킵니다.
Ex − xaabaazz… → xaabazzz… (의 경우 z로 바꾸고 왼쪽으로 이동)
상태 q3에서 전환
-
δ ( q3, z ) → ( q3, z, L ). 상태 q3에서 문자 읽기가 z이면 상태 q3에 머물고 왼쪽으로 이동하여 문자열의 이전 문자를 가리킵니다.
Ex − xaabzzzz... → xaabzzzz... (z의 경우 아무 것도 하지 않고 왼쪽으로 이동)
-
δ ( q3, b ) → ( q2, z, R ). 상태 q2에서 문자 읽기가 b이면 z로 만들고 stateq2에서 이동하고 문자열의 다음 문자를 가리키도록 오른쪽으로 이동합니다. 모든 b 교체
Ex − xaabzzzz… → xaazzzzz… (b의 경우 z로 교체하고 오른쪽으로 이동)
-
δ ( q3, a ) → ( q2, z, R ). 상태 q2에서 문자 읽기가 이면 z로 만들고 stateq3으로 이동하고 문자열의 다음 문자를 가리키도록 오른쪽으로 이동합니다. 모두 교체
Ex − xaazzzz… → xaazzzzz… (의 경우 z로 교체하고 오른쪽으로 이동)
-
δ ( q3, x ) → ( q4, z, R ). 상태 q2에서 문자 읽기가 x이면 z로 만든 다음 상태 q3으로 이동하고 문자열의 다음 문자를 가리키도록 오른쪽으로 이동합니다. 첫 번째 기호에 도달했습니다.
Ex − xzzzzzzzz… → zzzzzzzz… ( x는 z로 바꾸고 오른쪽으로 이동)
상태 q4에서 전환
-
δ ( q4, z ) → ( q4 z, R ). 상태 q4에서 문자 읽기가 z이면 상태 q4를 유지하고 문자열의 다음 문자를 가리키도록 오른쪽으로 이동합니다. 모든 문자는 이제 z입니다.
Ex − zzzzzzzz… → zzzzzzzz… (모든 z는 아무것도 하지 않고 오른쪽으로 이동)
-
δ ( q4, $ ) → ( qf, $ , R ). 상태 q4에서 문자가 남아 있지 않으면 끝에 도달했습니다. 최종 상태로 전환 qf. 즉, 문자열이 허용됩니다.
Ex − zzzzzzzz$ → zzzzzzzz (문자열 끝의 경우 $는 아무것도 하지 않고 최종 상태로 이동)
다이어그램은 튜링 머신을 보여줍니다 -
입력
aabaaaq0:aabaaa → q1:xabaaa → q1:xabaaa → q2:xabaaa → q3:xabzaa → q2:xazzaaq2:xazzaa → q3:xazzza → q3:xazzza → q3:xazzza → q2:xzz → q2:xzzzzzz → q2:xzzzzzz → q2:xzzzzzz → q3:xzzzzzz……..q3:xzzzzzz → q3:xzzzzzz → q4:zzzzzzz → q4:zzzzzzz…>도달한 qf는 aabaaa가 수락되었음을 의미합니다.