Задача "S-термы"
S-терм - это последовательность символов S и скобок, определяемая
рекурсивно следующим образом:
- символ S есть S-терм;
- если M и N - S-термы, то выражение (MN) есть также S-терм.
Пример S-терма: ((((SS)(SS))S)(SS)). Правые скобки не несут информации и
могут опускаться. В этом случае вышеприведенный S-терм выглядит так:
((((SS)(SS))S)(SS.
Задание 1. Напишите процедуру "gensterm" для порождения S-термов. Она должна для
заданного n заполнять n текстовых файлов (n = длина = число символов 'S'),
каждый из которых содержит все S-термы длины n = 1,2,...,n соответственно.
Внутри файла S-термы разделяются символом ';'. В конце каждого файла должен
стоять символ '.' (точка).
Напишите программу, которая по заданному целому n (n <= 10) выполняет
описанную выше процедуру и выдает на дисплей все сгенерированные S-термы.
Рассмотрим вычисление S-термов. Единственное алгебраическое правило
(S-правило), которое может быть использовано, состоит в следующем: любой
подтерм S-терма, имеющий вид (((SA)B)C), где A, B, C - также S-термы, может
быть переписан как ((AC)(BC)), то есть Context1(((SA)B)C)Context2 ->
Context1((AC)(BC))Context2.
Применение этого правила к S-терму называется редукцией S-терма. Возможны
разные способы (стратегии) выбора подтермов для применения S-правила.
Последовательное применение S-правила к S-терму до тех пор, пока это
возможно, называется нормализацией.
Пример цепочки редукции S-терма:
((((SS)(SS))S)(SS)) -> (((SS)((SS)((SS)S))(SS))
-> ((S(SS))(((SS)S)(SS))) -> ((S(SS))((S(SS))(S(SS)))).
Задание 2. Предложите эффективную структуру данных для представления S-термов, облегчающую применение S-правила. Напишите две процедуры: "readterm" и "printterm". Первая из них преобразует S-термы в Вашу структуру данных из формы, порождаемой процедурой "gensterm"; вторая преобразует S-термы из Вашей структуры в форму, порождаемую процедурой "gensterm". Ваша программа должна демонстрировать эти преобразования.
Задание 3. Напишите процедуру "reduce", выполняющую один шаг редукции в соответствии с S-правилом над заданным подтермом S-терма в Вашем представлении. Программа должна демонстрировать это.
Задание 4. Напишите процедуру "normalize", которая в заданном S-терме должна последовательно выбирать подтермы и применять S-правило до тех пор, пока дальнейшии редукции станут невозможными, либо число шагов не достигнет некоторого максимума, например 30. Ваша программа должна демонстрировать это.
Задание 5. Объедините все процедуры в одну программу, которая:
- запрашивает у пользователя длину n;
- порождает с помощью процедуры "gensterm" S-термы заданной длины;
- преобразует все S-термы в Ваше представление;
- нормализует их (если это возможно);
- выводит в качестве результата нормализованные S-термы;
- выводит последовательно число шагов редукции, совершенных над каждым S-термом, либо сообщение "not normalized", если нормализация требует более 30 шагов;
- выводит число ненормализованных термов и общее число всех S-термов заданной длины n.
