Задачи для решения

Замечания:

1.В задачах рассматриваются только целые неотрицательные числа, если не сказано иное.

2. Под «единичной» системой счисления понимается запись неотрицательного целого числа с помощью палочек - должно быть выписано столько палочек, какова величина числа;

например: 2→| | , 5 → | | | | | , 0 → <пустое слово>.

1. A={a,b,c}. Приписать слева к слову P символ b (P → bP).

2. A={a,b,c}. Приписать справа к слову P символы bc (P →Pbc).

3. A={a,b,c}. Заменить на a каждый второй символ в слове P.

4. A={a,b,c}. Оставить в слове P только первый символ (пустое слово не менять).

5. A={a,b,c}. Оставить в слове P только последний символ (пустое слово не менять).

6. A={a,b,c}. Определить, является ли P словом ab. Ответ (выходное слово): слово ab, если является, или пустое слово иначе.

7. A={a,b,c}. Определить, входит ли в слово P символ a. Ответ: слово из одного символа a (да, входит) или пустое слово (нет).

8. A={a,b,c}. Если в слово P не входит символ a, то заменить в P все символы b на с, иначе в качестве ответа выдать слово из одного символа a.

9. A={a,b,0,1}. Определить, является ли слово P идентификатором (непустым словом, начинающимся с буквы). Ответ: слово a (да) или пустое слово (нет).

10. A={a,b,0,1}. Определить, является ли слово P записью числа в двоичной системе счисления (непустым словом, состоящем только из цифр 0 и 1). Ответ: слово 1 (да) или слово 0.

11. A={0,1}. Считая непустое слово P записью двоичного числа, удалить из него незначащие нули, если такие есть.

Практическая работа №2 Сравнение символов, стирание слова, удаление символа из слова.

Пример 1 (сравнение символов, стирание слова) А={a,b,c}. Если первый и последний символы (непустого) слова Р одинаковы, тогда это слово не менять, а иначе заменить его на пустое слово.

Решение.

Для решения этой задачи предлагается выполнить следующие действия:

1.Запомнить первый символ входного слова, не стирая его.

2. Переместить автомат под последний символ и сравнить его с запомненным. Если они равны, то больше ничего не делать.

3.В противном случае уничтожить всё входное слово.

Как запоминать символ и как перегонять автомат под последний символ слова, мы уже знаем из предыдущих примеров. Стирание же входного слова реализуется заменой всех его символов на символ Л. При этом, раз уж автомат оказался в конце слова, будем перемещать автомат справа налево до первой пустой клетки.

Эти действия описываются следующей программой для МТ (напомним, что крестик в ячейке таблицы означает невозможность появления соответствующей конфигурации при выполнении программы):

Пример 2 (удаление символа из слова) А={а,b}. Удалить из слова Р его второй символ, если такой есть.

Решение.

Казалось бы, эту задачу решить просто: надо сдвинуть автомат под клетку со вторым символом и затем очистить эту клетку:

Однако напомним, что внутри выходного слова не должно быть пустых клеток. Поэтому после удаления второго символа надо «сжать» слово, перенеся первый символ на одну клетку вправо. Для этого автомат должен вернуться к первому символу, запомнить его и стереть, а затем, снова сдвинувшись вправо, записать его в клетку, где был второй символ.

Однако начальный «поход» вправо ко второму символу, чтобы его стереть, и последующий возврат к первому символу являются лишними действиями: какая разница - переносить первый символ в пустую клетку или в клетку с каким-то символом? Поэтому сразу запоминаем первый символ, стираем его и записываем вместо второго символа:

В виде программы для МТ всё это записывается так: