Тема 2.2 Универсальные машины и универсальные функции

Тема 2.2 Универсальные машины и универсальные функции

Нормальные алгоритмы Маркова

Цель:формирование умения разрабатывать НАМ.

Ход занятия:

1) Повторить теоретический материал предыдущих занятий.

2) Решить 3 задачи. Решения отправить на проверку.

1 Дан алфавит A = {a, b, c}. Перенести в начало слова все буквы a.

2 Дан алфавит A = {a, b, c}. Упорядочить буквы в слове P по алфавиту.

3 Дан алфавит A = {a, b, c}. Написать 1, если входное слово P нечётной длины, иначе написать 2.

4 Дан алфавит A = {a, b, c}. Переставить первую букву слова P в его конец.

5 Дан алфавит A = {a, b, c}. Удвоить каждую букву слова P .

6 Дан алфавит A = {a, b, c} Удалить второе вхождение a.

7 Дан алфавит A = {a, b, c}. Заменить во входном слове P все вхождения ba на a.

8 Дан алфавит A = {a, b}. Удалить во входном слове P два последних вхождения буквы a. Пример: aabaababb → aababbb.

9 Дан алфавит A = {a, b}, входное слово P чётной длины. Стереть правую половину слова P . Пример: babbaa → bab.

10 Дан алфавит A = {a, b}. Обратить входное слово P . Пример: babbaa → aabbab.

11 Дан алфавит A = {a, b, c}. Приписать к концу P столько палочек, сколько раз буква b входит в P . Пример: abcbb → abcbb

. 12 Дан алфавит A = {a, b}. Удвоить входное слово P :P →PP. Пример: abb → abbabb.