Машина Тьюринга, принимающая строки с одинаковой начальной и конечной длиной

Мне нужна помощь в создании одноленточной детерминированной машины Тьюринга для этого языка введите здесь описание изображения

здесь я не уверен, как определить, какие строки примет ТМ. Как я могу заставить машину принимать строки, где a=c? потому что часть b содержит элементы как из a, так и из c.


computation turing-machines finite-automata
person user14864    schedule 22.03.2014    source источник
comment
Вы пробовали что-то?   -  person Benoît Guédas    schedule 22.03.2014
comment
@ BenoîtGuédas да, но я не знаю ключевого замечания, какие строки будут приняты, в этом есть некоторая хитрость. точно знаю только, что это C, если 3 идет после 2, и это B, если 1 идет после 2, но для всех остальных случаев я не уверен, как определить, где начинается и заканчивается B и где начинается C и заканчивается   -  person user14864    schedule 22.03.2014

Ответы (1)


arrow_upward
1
arrow_downward

Может быть, вы можете попробовать адаптировать машину, которая принимает палидромы: вы читаете символ слева. Если он принадлежит {0,1}, вы удаляете его и идете вправо (последний символ). Если символ принадлежит {2,3}, вы удаляете его и возвращаетесь влево (первый символ). Повторяйте это до тех пор, пока не найдете символ, который не принадлежит стороне "a" или "c" (и проверьте последний символ, если вы были слева), остальные символы должны принадлежать блоку "b".

person Benoît Guédas    schedule 22.03.2014