Задание на лабораторную работу

1. Составить нормальный алгоритм Маркова над алфавитом А.

2. На конкретных примерах исходных слов продемонстрировать работу составленных алгоритмов.

Варианты заданий

1. Реализовать алгоритм, выполняющий замену в слове в алфавите каждого символа на символ .

2. Реализовать алгоритм, выполняющий перестановку в слове в алфавите букв таким образом, чтобы сначала стояли все нули, а затем все единицы.

3. Составить нормальный алгоритм, преобразующий исходную строку в алфавите в строку, в которой буквы расположены в алфавитном порядке.

4. Реализовать алгоритм, выполняющий над числами в унарном коде.

5. Реализовать алгоритм, выполняющий над числами в унарном коде.

6. Реализовать алгоритм, выполняющий над числами в унарном коде.

7. Реализовать алгоритм, вычисляющий арифметическое вычитание в унарном коде.

8. Реализовать функцию выбор аргумента над числами в унарном коде.

9. Реализовать вычисление предиката X=Y в унарном коде с сохранением (восстановлением) исходных данных.

10. Реализовать вычисление предиката X>Y в унарном коде с сохранением (восстановлением) исходных данных.

11. Реализовать алгоритм в алфавите , меняющий местами первую и последнюю буквы слова.

12. Реализовать алгоритм над алфавитом , меняющий местами первый ноль и последнюю единицу.

13. Реализовать операцию копирование в алфавите , то есть получить из слова слово .

14. Реализовать алгоритм над алфавитом , который выдает единицу, если в исходном слове только парные нули и ноль в противном случае.

15. Реализовать алгоритм в алфавите , который переставляет буквы в слове так, чтобы сначала шли все нули, потом – единицы.

16. Реализовать алгоритм над алфавитом , исключающий в слове последнюю звездочку.

17. Реализовать алгоритм, реализующий функцию циклический сдвиг двоичного числа на одну ячейку.

18. Реализовать алгоритм в алфавите , анализирующий последовательность цифр в слове и выдающий «+», если цифры образуют неубывающую последовательность, и «–» в противном случае.

19. Реализовать алгоритм над алфавитом , который выдает 1, если исходное слово содержит комбинацию baccd, и 0 - в противном случае.

20. Реализовать алгоритм, выполняющий следующие действия. В слове в алфавите стереть все, кроме . Если такой последовательности нет, все стереть.

21. Реализовать алгоритм над алфавитом , переставляющий буквы в обратном порядке.

22. Реализовать алгоритм над алфавитом , который выдает 1, если в исходном слове содержатся только парные нули, и 0 - в противном случае.

23. Реализовать алгоритм над алфавитом , который выдает «да», если в исходном слове четное количество y-ков, и «нет» в противном случае.

24. Реализовать алгоритм над алфавитом , выдающий в результате столько единиц, сколько нулей в исходном слове.

25. Реализовать алгоритм над алфавитом , выделяющий часть слова расположенную между первой парой звездочек.

Контрольные вопросы

1. Что такое Марковская подстановка?

2. Что такое заключительная Марковская подстановка, как она обозначается?

3. В каком случае Марковская подстановка считается неприменимой к некоторому слову?

4. Как функционирует нормальный алгоритм Маркова?

5. В каких случаях НАМ заканчивает работу и останавливается?

6. Чем отличается НАМ в алфавите А от алгоритма над алфавитом А?

7. Привести пример бесконечно работающего нормального алгоритма Маркова.

8. Привести определение нормально вычислимой словарной функции.

9. Сформулировать принцип нормализации.