2. Примеры нормальных алгоритмов

Пример 2. Нормальный алгоритм в алфавите , перерабатывающий каждое слово вида * в слово *а , где  - слово, состоящее из букв a,b.

*a*a

*bb*

* a

.*

Пусть  = abb. Тогда последовательность преобразований имеет вид :

Пример 3. Нормальный алгоритм над алфавитом , стирающий все символы входного слова до первого символа «2» включительно.

Здесь вспомогательными являются буквы x и y , таким образом, алфавит . Буква х служит для того, чтобы найти букву 2 последовательным перебором слева направо, буква y позволяет стереть буквы 0,1,2 движением справа налево. Можно заметить аналогию между буквами x и y и головкой машины Тьюринга.

Пример функционирования приведенного алгоритма по переработке слова 101201 :

Пример 4. Нормальный алгоритм над алфавитом , который выдает «и», если в исходном слове, состоящем из нулей единиц, есть комбинация 1101, и «л» - в противном случае.

Приведем два примера функционирования этого алгоритма :

1. 

2. 

ЛИТЕРАТУРА

1. Алферова З.В. Теория алгоритмов. -М.:Статистика,1973.-164с.

2. Криницкий Н.А. Алгоритмы вокруг нас. -М : Наука, 1977.-126с.

3. Криницкий Н.А. Миронов Г.А., Фролов Г.Д. Программирование и алгоритмические языки. -М.Наука, 1979.-496с.

4. Кузнецов О.П. Адельсон-Вельский Г.М. Дискретная математика для инженера. -М.: Энергия, 1980.-344с.

5. Мальцев А.И. Алгоритмы и рекурсивные функции. -М.Наука, 1965.-392с.

6. Петер Р. Рекурсивные функции. -М.ИЛ, 1954.-366с.

7. Трахтенберг Б.А. Алгоритмы и вычислительные автоматы. -М.: Советское радио, 1974.-200с.

8. Шоломов Л.А. Основы теории дискретных логических и вычислительных устройств. -М.:Наука, 1980.-400с.

9. Гаврилов Г.П. , Сапоженко А.А. Сборник задач по дискретной математике.-М.:Наука, 1977.-368с.

10. Лавров И.А. , Максимов Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов.-М.:Наука, 1975.-240с.