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

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. Сформулировать принцип нормализации.