Переписывание пары букв в МТ

[Farid123]

Предположим у нас есть последовательность букв. Если в этой последовательности есть пара букв $XY$ ,то эту пару нужно заменить на $Z$ , при этом никаких пробелов быть не должно. Все это должно происходить в Машине Тюринга. Идея была такова. Пусть сначала машина чиатеат первую букву, если не $X$ идет направо , если $X$ то опять направо . Если после $X$ идёт $Y$ то 1 шаг налево , вместо $X$ написать $Z$. Затем опять направо удалить $Y$.Теперь тут возникает пустота.чтобы её устранить я просто хотел сместить каждую букву после пустоты на 1 слот.Тоесть Машина после пустоты идёт направо , читатет букву, возвращается налево и пишет эту букв.Затем на 2 шага вправо , опять читает, на 1 шаг влево и пишет ту букву и так далее. Как собственно это изобразить , и если возможно то упростить эту схему как то?

[mihaild]

В каком смысле "изобразить"? Можно например явно выписать какие состояния тут нужны и нарисовать картинку со стрелками - из каждого состояния для каждого символа по стрелке, на каждой стрелке подписано для какого символа эта стрелка и что мы пишем в текущую позицию при этом переходе.

Хороших способов упростить я не вижу, МТ низкоуровневая штука.

[feedinglight]

МТ можно использовать как процедурный ЯП. Если 1 раз настроить МТ на какую-то процедуру типа "убрать пробелы в строке", то можно считать что эта операция уже есть, и не заморачиваться с нумерацией состояний и прочим. Ну и из элементарных операций потом на полу-автомате собирать машины для разных задач. Это может немного ухудшать скорость машины, но её запускать всё равно никто не будет.

[Dmitriy40]

Farid123
Приведённый алгоритм не обрабатывает множественные вхождения $XY$, это так и должно быть или забыли?
Способов упростить я тоже не вижу.

[Farid123]

Dmitriy40
Можно ли как то этот алгоритм циклически повторять после каждой замены пары двух символов на одну?

-- 21.02.2020, 18:46 --

feedinglight
Задача в том что нельзя просто взять и убрать пробел

[Dmitriy40]

Farid123 в сообщении #1440717 писал(а):

Dmitriy40
Можно ли как то этот алгоритм циклически повторять после каждой замены пары двух символов на одну?

Можно, причём множеством способов.

[Farid123]

Dmitriy40
Как это на схеме отобразить , типо последний такт смещения букв соединить с начальным состоянием ?. Тоесть насколько я понимаю она должна быть замкнутым циклом.

[Dmitriy40]

Farid123 в сообщении #1440726 писал(а):

Тоесть насколько я понимаю она должна быть замкнутым циклом.

Ну да, например обернуть весь блок поиска и замены одной комбинации во внешний цикл с условием выхода по ненахождению $XY$ (придётся ещё перегнать каретку влево до конца). Но есть и другие варианты, более сложные, зато и более производительные.

[Farid123]

Dmitriy40
С логикой вроде как разобрался. Кстати часть где нужно смещать буквы из-за возникающей пустоты можно тоже задать циклически потому что по сути всегда принцип один и тот же. Остаётся лишь на схеме это изобразить что является довольно проблематичной потому что состояний много + 2 важные петли нужно грамотно изобразить. Не могли бы посоветовать как изобразить цикл для смещения букв дабы убрать пустоту?

[Dmitriy40]

Farid123 в сообщении #1440747 писал(а):

Не могли бы посоветовать как изобразить цикл для смещения букв дабы убрать пустоту?

Начальное состояние: позиция над буквой Z, справа Y, состояние каретки Q0.
Состояние       Символ ленты            Новое состояние         Действие
Q0              любой                   Q1                      сместиться вправо
Q1              любой                   Q2                      сместиться вправо
Q2              пустой                  QE                      по желанию, конец
Q2              не пустой, K            QK                      сместиться влево
QK              любой                   Q0                      записать на ленту символ K
QE, конец цикла

Как-то так. QK — не одно состояние, а K почти одинаковых, отличающихся лишь символом из допустимого алфавита. В Q2 можно записать в конец ленты пустоту, при желании.

[feedinglight]

Farid123 в сообщении #1440717 писал(а):

Задача в том что нельзя просто взять и убрать пробел

Я писал не о задаче, а об её оформлении. В данном случае машину можно оформить в виде процедурного псевдокода.
Например, набор процедур(каждая процедура - МТ):

FIND_XY_CLEAR. Идти направо, найти и заменить на пробелы XY. Выходное состояние 1 если найдено, выходное состояние 2 если не найдено.
DEL_SPACES. Удалить пробелы в строке.

и другие мелкие процедуры, которые могут использоваться этих процедурах.

Например, псевдокод машины:

1. Повторять FIND_XY_CLEAR пока выходное состояние 1.
2. Выполнить DEL_SPACES

Останется просто скомпилировать - подставить в псевдокод процедуры.
Если так строить машины, то машина получается не самая маленькая, зато минимальная внимательность требуется только на стадии компиляции, а отдельные процедуры простые и их можно многократно использовать.
Хотя, в данном случае я бы сразу машину построил, т.к. задача слишком простая. Зависит от ресурса внимательности и сложности задачи, не знаю короче, забейте, ладно.

[Farid123]

Dmitriy40
Спасибо, попробую.

[Farid123]

Dmitriy40
При отображении внешнего цикла на рисунке можно ли просто последнее состояние соеденить с $q_0$ начальным состоянием?

[Dmitriy40]

Farid123
Нельзя, ведь каретка кажется не обязана стоять в позиции первого уже найденного $XY$, Вы же сами писали что сначала каретка читает самую левую позицию. А я привёл кусок алгоритма лишь удаления пустого места, с другим начальным состоянием, соответственно Вам придётся дописать процедуру перехода между этими начальными состояниями. Это наверняка можно сделать разными способами.

[Farid123]

Dmitriy40
Не на позиции найденного ${XY}$ я имею ввиду, а на позиции самой первой буквы. Тоесть после того как машина разобралась с пустотами и на последнем цикле когда видет что уже при смещении направо идёт не буква а опять пустота, то она возвращается к самой первой букве чтоб продолжить поиск пары ${XY}$. Иными словами чтобы обобщить процесс перегонки каретки с правой стороны к первой букве.