여기에서 언어 L ={WW r 을 위한 튜링 기계를 만드는 방법을 볼 것입니다. |W는 {0, 1}}에 속합니다. 따라서 이것은 0과 1의 두 문자만 사용하는 일종의 언어를 나타냅니다. w는 문자열이고 w r 그것의 반대입니다. 따라서 w =10110이면 w r 01101이 됩니다. 따라서 튜링 기계는 문자열 z =1011001101을 받아들입니다.
이를 해결하기 위해 이 접근 방식을 사용합니다. 먼저 첫 번째 기호를 확인하고 0이면 y로 바꾸고 1이면 x로 바꾸세요. 그런 다음 문자열의 끝으로 이동합니다. 따라서 마지막 기호는 첫 번째 기호와 동일합니다. 그것에 따라 x 또는 y로도 대체합니다. 그런 다음 다시 처음부터 기호 교체 옆의 위치로 돌아와 위에서 언급한 동일한 과정을 반복합니다. w r 이후로 w의 반대는 둘 다 동일한 수의 기호를 갖습니다. 문자열의 처음부터 n번째 기호를 교체할 때마다 끝에서 해당하는 n번째 기호를 교체합니다.
상태 전환 다이어그램
