여기에서 언어 L ={AiBjCk | 나는> j> k; k ≥ 1}. 그래서 이것은 우리가 단지 3개의 문자, b, c를 사용하는 일종의 언어를 나타냅니다. w는 문자열입니다. 따라서 w =aaaaaabbbbccc이면 튜링 기계가 이를 받아들입니다.
이를 해결하기 위해 이 접근 방식을 사용합니다. 먼저 A와 D를 단일 요소로 만들어 두 요소를 비교한 다음 C의 개수가 |(A, D)|보다 크면 A와 D를 비교한 다음 |D|인 경우 문자열이 허용되지 않습니다.> |A|, 그렇지 않으면 승인됩니다.
상태 전환 다이어그램
