Дан внешний алфавит {a,b}.
Нужно заменить буквы первой половины входного слова на "а".
Не понимаю как заставить машину узнавать половину слова..
Объясните, пжлста, кто разбирается. Заранее благодарю.
Здравствуйте, sendo, Вы писали:
S>Дан внешний алфавит {a,b}.
S>Нужно заменить буквы первой половины входного слова на "а".
S>Не понимаю как заставить машину узнавать половину слова..
S>Объясните, пжлста, кто разбирается. Заранее благодарю.
Пусть есть язык L = {w^2n|n принадлежит N, w принадлежит {a,b}}
Сделаем следующим образом:
1. Поиск середины слова.
Берем первый входной символ из алфавита {a,b} на A или B соответственно, далее перемащаемся по
ленте до её конца и производим замену строчной буквы на прописную. Потом идем обратно в начало ленты
и заменяем вторую букву и так далее....:
ababba -> Ababba -> AbabbA -> ABabbA -> ABabBA -> ABAbBA -> ABA!BBA
Кода цепочка кончилась головка машины аккурат находится по середине цепочки.
2. Идем в лево и заменяем все символы на a.
3. Идем назад в право пока не встретим прописной символ.
4. Продолжая движения направо, производим обратную замену прописных на строчные.
ИХМО усе, надеюсь общую идею алгоритма объяснил
Спасибо. Все верно.
Спасибо. Mab предложил тоже самое, но менее развернуто.
Я писал еще в другом форуме — там предлагали ставить после каждой второй буквы единицу и потом вернуться обратно на столько шагов, сколько единиц у меня получиться. Но это всё врядли применимо к Тьюрингу. По вашим советам я написал решение за три минуты.
