Базис класса стандартных схем программ
Стандартные схемы программ (ССП) характеризуются базисом и структурой схемы.
Базис класса фиксирует символы, из которых строятся схемы, указывает их роль (переменные, функциональные символы и др.), задает вид выражений и операторов схем.
Полный базис В класса стандартных схем состоит из 4-х непересекающихся, счетных множеств символов и множества операторов - слов, построенных из этих символов.
Множества символов полного базиса:
1. Х = {x, х1, х2..., у, у1 у2..., z, z1, z2...} - множество символов, называемых переменными;
2. F = {f(0), f(1), f(2)..., g(0), g(1), g(2)..., h(0), h(1), h(2)...} - множество функциональных символов; верхний символ задает местность символа; нульместные символы называют константами и обозначают начальными буквами латинского алфавита a, b, c...;
3. Р = {р(0), р(1), р(2)...; q(0), q(1), q(2)...; } - множество предикатных символов; р(0), q(0) - ; нульместные символы называют логическими константами;
4. {start, stop, ..., :=и т. д.} - множество специальных символов.
Термами (функциональными выражениями) называются слова, построенные из переменных, функциональных и специальных символов по следующим правилам:
1.односимвольные слова, состоящие из переменных или констант, являются термами;
2.слово τ вида f(n)(τ1, τ2, ..., τn), где τ1, τ2, ..., τn- термы, является термом;
3.те и только те слова, о которых говорится в п.п. 1,2, являются термами.
Примеры термов: х, f(0), а, f(1)(х), g(2)(x, h(3)(y, a)).
Тестами (логическими выражениями) называются логические константы и слова вида р(n)(τ1, τ2,..., τn). Примеры: p(0), p(0)(х), g(3)(x, y, z), p(2)(f(2)(x, y)). Допускается в функциональных и логических выражениях опускать индексы местности, если это не приводит к двусмысленности или противоречию.
Множество операторов включает пять типов:
1. начальный оператор - слово вида start(х1, х2...хк), где k ≥0, а х1, х2...хк - переменные, называемые результатом этого оператора;
2. заключительный оператор - слово вида stop(τ1, τ2,..., τn), где n ≥ 0, а τ1, τ2,..., τn - термы; вхождения переменных в термы τ называются аргументами этого оператора;
3. оператор присваивания - слово вида х := τ, где х – переменная (результат оператора), а τ - терм; вхождения переменных в термы называются аргументами этого оператора;
4. условный оператор (тест) - логическое выражение; вхождения переменных в логическое выражение называются аргументами этого оператора;
5. оператор петли - односимвольное слово loop.
Среди операторов присваивания выделим случаи: когда τ - переменная, то оператор называется пересылкой (х:=у) и когда τ - константа, то оператор называется засылкой (х:=а).
Подклассы используют ограниченные базисы. Так, например, подкласс V1 имеет базис: {х1, х2}, {а, f(1)}, {p(1)},{start,stop, (,),:=, ,} и множество операторов {start(х1, х2); х1:=f(x1), x2:=f(x2), x1:=а, х2:= а, р(х1), р(х2), stop(х1, х2)}, т. е. схемы из этого подкласса используют две переменные, константу а, один одноместный функциональный символ, один предикатный символ и операторы указанного вида.
Дата добавления: 2015-07-18; просмотров: 1691;