Архив рубрики: Теория алгоритмов

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

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

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

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

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

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

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