Любая строка a ^ (3 ^ n) для n> = 0 имеет номер a, который либо один, либо делится на три равных.Мы можем использовать это следующим образом:
- вычеркивать 2 экземпляра a на конце строки для каждого 1 экземпляра a на фронте
- повторять до тех пор, пока не останется только одиноставшиеся, затем прекратите принимать
- , если в любой момент вы не можете следовать правилам 1 и 2, прекратите отклонение
Реализация этой идеи заключается в следующем
Q T Q' T' D comment
q0 a q1 A right ensure at least one a
q1 a q2 a right if multiple a, keep going
q1 # h_a # left if one a, halt accept
q2 a q2 a right scan all the way to the end
q2 # q3 # left go to last a
q3 a q4 # left erase it, go to new last a
q4 a q5 # left erase it, go to new last a
q5 a q5 a left scan back to the first marked a
q5 A q6 A right
q6 a q2 A right have another a, start scanning again
q6 # q7 # left no more a, reset tape
q7 A q7 a left scan to beginning, unmarking all a
q7 # q0 # right start process over from the beginning
Этот TM работает путем итеративного преобразования входной ленты a ^ (3 ^ n) в ^ (3 ^ (n-1)) до тех пор, пока она не станет ^ 1 или не разделится равномерно на некотором этапе.
Пример:
001 002 003 004
#aaaaaaaaa# #Aaaaaaaaa# #Aaaaaaaaa# #Aaaaaaaaa#
^ ^ ^ ^
q0 q1 q2 q2
005 006 007 008
#Aaaaaaaaa# #Aaaaaaaaa# #Aaaaaaaaa# #Aaaaaaaaa#
^ ^ ^ ^
q2 q2 q2 q2
009 010 011 012
#Aaaaaaaaa# #Aaaaaaaaa# #Aaaaaaaaa# #Aaaaaaaa##
^ ^ ^ ^
q2 q2 q3 q4
013 014 015 016
#Aaaaaaa### #Aaaaaaa### #Aaaaaaa### #Aaaaaaa###
^ ^ ^ ^
q5 q5 q5 q5
017 018 019 020
#Aaaaaaa### #Aaaaaaa### #Aaaaaaa### #Aaaaaaa###
^ ^ ^ ^
q5 q5 q5 q6
021 022 023 024
#AAaaaaa### #AAaaaaa### #AAaaaaa### #AAaaaaa###
^ ^ ^ ^
q2 q2 q2 q2
025 026 027 028
#AAaaaaa### #AAaaaaa### #AAaaaaa### #AAaaaa####
^ ^ ^ ^
q2 q2 q3 q4
029 030 031 032
#AAaaaa#### #AAaaaa#### #AAaaaa#### #AAaaa#####
^ ^ ^ ^
q5 q5 q5 q5
033 034 035 036
#AAaaa##### #AAAaa##### #AAAaa##### #AAAaa#####
^ ^ ^ ^
q6 q2 q2 q2
037 038 039 040
#AAaaa##### #AAAa###### #AAA####### #AAA#######
^ ^ ^ ^
q3 q4 q5 q6
041 042 043 044
#AAA####### #AAa####### #Aaa####### #aaa#######
^ ^ ^ ^
q7 q7 q7 q7
045 046 047 048
#aaa####### #Aaa####### #Aaa####### #Aaa#######
^ ^ ^ ^
q0 q1 q2 q2
049 050 051 052
#Aaa####### #Aa######## #A######### #A#########
^ ^ ^ ^
q3 q4 q5 q6
053 054 055 056
#A######### #a######### #a######### #a#########
^ ^ ^ ^
q7 q7 q0 q1
049
#a#########
^
h_a