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

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

* a ®* a

* b ® b*

*® a

®.*

Пусть 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с.

Дата добавления: 2014-01-07