여기에서 언어 L ={AiBjCk | 나는 * j =k; i, j, k ≥ 1}. 따라서 이것은 A, B, C 세 개의 문자만 사용하는 일종의 언어를 나타냅니다. w는 문자열입니다. 따라서 w =AABBBBCCCCCCCC이면 튜링 기계가 이를 받아들입니다.
이를 해결하기 위해 이 접근 방식을 사용할 것입니다.
-
먼저 A를 x로 바꾸고 오른쪽으로 이동합니다. 그런 다음 모든 A를 건너뛰고 오른쪽으로 이동하세요.
-
머리가 첫 번째 B에 도달하면 하나의 B를 y로 교체한 다음 모든 중간 B를 건너뛰고 교체된 B에 해당하는 오른쪽으로 이동하여 이제 하나의 C를 z로 교체하고 왼쪽으로 이동합니다.
-
이제 도중에 z와 B를 모두 건너뛰고 왼쪽으로 이동합니다.
-
포인터가 최근 y에 도달하면 오른쪽으로 이동합니다.
-
포인터가 B를 가리키고 있으면 2-4단계를 반복하고, 그렇지 않으면 포인터가 z를 가리킬 때 왼쪽으로 이동하면서 y를 모두 B로 바꾸고 모든 A를 건너뜁니다.
-
포인터가 가장 최근 x에 올 때 오른쪽 단계로 이동합니다.
-
포인터가 여전히 A를 가리키고 있으면 위의 모든 단계를 반복하고, 그렇지 않으면 머리가 y에 있을 때 y와 z를 모두 건너뛰고 오른쪽으로 이동합니다.
-
$에 도달하면 왼쪽으로 이동합니다. 문자열이 허용됩니다.
상태 전환 다이어그램
