여기에서 언어 L ={0n1n2n | n ≥ n}. 따라서 이것은 0, 1 및 2의 세 문자만 사용하는 일종의 언어를 나타냅니다. w는 문자열입니다. 따라서 w =000111222이면 튜링 기계가 이를 수락합니다.
이를 해결하기 위해 이 접근 방식을 사용합니다. 먼저 앞에서 하나의 0을 x로 바꾼 다음 하나가 1이 될 때까지 오른쪽으로 계속 이동하고 이 1을 y로 바꿉니다. 다시 1이 될 때까지 오른쪽으로 계속 이동하고 z로 바꾸고 왼쪽으로 이동합니다. 이제 하나의 x를 찾을 때까지 왼쪽으로 계속 이동합니다. 얻을 때 오른쪽으로 이동한 다음 위와 동일한 절차를 따르십시오.
x 바로 다음에 y가 오는 경우 조건이 발생합니다. 이 시점에서 우리는 계속 오른쪽으로 이동하고 모든 1과 2가 y와 z로 변환되었는지 여부를 계속 확인합니다. 그렇지 않으면 문자열이 허용되지 않습니다. $에 도달하면 문자열이 허용됩니다.
상태 전환 다이어그램
