Лабораторная работа «Нормальные алгоритмы Маркова».

Лабораторная работа №14

Тема: «Нормальные алгоритмы Маркова».

Цель: научится составлять в Turbo Pascal программы для вычисления нормальных алгоритмов Маркова.

Основная операция при работе алгоритмов Маркова – это переработка слов в некотором алфавите. Эта переработка заключается в производстве некоторого количества замен определенных последовательностей символов. Эти замены совершаются в строго определенном порядке, а именно: после каждой замены алгоритм читается с самого начала, а слово анализируется с самого первого символа. В отличие от машин Тьюринга, алгоритмы Маркова выполняются без какого – либо устройства, осуществляющего движения и имеющего внутреннюю память. В данном случае мы можем оперировать только ленточными знаками. Сама лента в этом случае не разделяется на строгие ячейки, а имеет гибкую основу, что позволяет ей растягиваться и сжиматься исходя из того, увеличивается ли в слове число символов или уменьшается.

Задание 1. Реализовать на языке Turbo Pascal следующую задачу: выяснить, есть ли в слове X буква "k", и, если есть, то замените все буквы "а" в этом слове на "с"

Напишите в Turbo Pascal код программы.

Задание 2. Измените код программы таким образом, чтобы программа подсчитывала количество букв «а» в слове.

Задание 3. Измените код программы, таким образом, чтобы все буквы «о» заменялись на «а».

Задание 4. Ответьте на контрольные вопросы:

1. Что представляет собой алгоритм Маркова?

2. Назовите основную операцию при работе алгоритма Маркова. В чем ее суть?

3. Чем отличается выполнение алгоритмов Маркова от машины Тьюринга?

4. Какой формат команд алгоритма Маркова?