Архив рубрики: Задачи

Уменьшение слова в три раза

Задача. На ленте машины Тьюринга находится слово, состоящее из 3n букв алфавита a. Уменьшите это слово в три раза.

Для выполнения данной задачи будем использовать эмулятор машины Поста ALGO2000. Сразу представим наш алгоритм, а чуть ниже разберемся с принципом его работы.

Лаб1(рабочая)

Перед началом работы каретка находится над крайним правым символом. Опишем каждое из состояний при n>0:

Q_0: Удаляет a, передвигает каретку влево и переходит в состояние Q_1;

Q_1: Удаляет a, передвигает каретку влево и переходит в состояние Q_2;

Q_2: Вписывает в ячейку a (по сути, не изменяет содержимое), передвигает каретку влево и переходит в состояние Q_3;

 

 

Алгоритм распознавания имени

Рассмотрим следующую задачу:

Построить нормальный алгоритм Маркова, распознающий ВАШЕ имя.

Для выполнения данной задачи будем использовать эмулятор машины Поста ALGO2000. Для простоты ограничимся буквами Вашего имени плюс любые две (в приведенной ниже реализации алгоритма без проблем можно увеличить количество).

Смысл алгоритма состоит в том, чтобы на первом шаге заменить ИМЯ целиком на некоторую переменную «x». Если строка содержит одно только имя, то за два прохода мы получим «ДА» (первая итерация строка №1, вторая итерация строка №28).

Если же помимо имени в исходной строке существует какой-либо «мусор» (при этом имени может в принципе и не быть), то с помощью некоторого количества итераций в исходной строке появится одна лишь переменная «y» (строка №26), позволяющая написать «НЕТ» (строка №27).

Лаб4(рабочая)