Базис класса стандартных схем программ

Стандартные схемы программ (ССП) характеризуются базисом и структурой схемы.

Базис класса фиксирует символы, из которых строятся схемы, указывает их роль (переменные, функциональные символы и др.), задает вид выражений и операторов схем.

Полный базис В класса стандартных схем состоит из 4-х непересекающихся, счетных множеств символов и множества операторов - слов, построенных из этих символов.

Множества символов полного базиса:

1. Х = { x, х₁, х₂..., у, у₁ у₂..., z, z₁, z₂...} - множество символов, называемых переменными;

2. F = { f ⁽⁰⁾, f ⁽¹⁾, f ⁽²⁾..., g ⁽⁰⁾, g ⁽¹⁾, g ⁽²⁾..., h ⁽⁰⁾, h ⁽¹⁾, h ⁽²⁾...} - множество функциональных символов; верхний символ задает местность символа; нульместные символы называют константами и обозначают начальными буквами латинского алфавита a, b, c...;

3. Р = { р ⁽⁰⁾, р ⁽¹⁾, р ⁽²⁾...; q ⁽⁰⁾, q ⁽¹⁾, q ⁽²⁾...; } - множество предикатных символов; р ⁽⁰⁾, q ⁽⁰⁾ -; нульместные символы называют логическими константами;

4. { start, stop,...,:= и т. д.} - множество специальных символов.

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

1.односимвольные слова, состоящие из переменных или констант, являются термами;

2.слово τ вида f ⁽ⁿ⁾(τ₁, τ₂,..., τ _n), где τ₁, τ₂,..., τ _n - термы, является термом;

3.те и только те слова, о которых говорится в п.п. 1,2, являются термами.

Примеры термов: х, f ⁽⁰⁾, а, f ⁽¹⁾(х), g ⁽²⁾(x, h ⁽³⁾(y, a)).

Тестами (логическими выражениями) называются логические константы и слова вида р ⁽ⁿ⁾(τ₁, τ₂,..., τ _n). Примеры: p ⁽⁰⁾, p ⁽⁰⁾(х), g ⁽³⁾(x, y, z), p ⁽²⁾(f ⁽²⁾(x, y)). Допускается в функциональных и логических выражениях опускать индексы местности, если это не приводит к двусмысленности или противоречию.

Множество операторов включает пять типов:

1. начальный оператор - слово вида start (х_1,х₂...х_к), где k ≥0, а х_1,х₂...х_к - переменные, называемые результатом этого оператора;

2. заключительный оператор - слово вида stop (τ₁, τ₂,..., τ _n), где n ≥ 0, а τ₁, τ₂,..., τ _n - термы; вхождения переменных в термы τ называются аргументами этого оператора;

3. оператор присваивания - слово вида х:= τ, где х – переменная (результат оператора), а τ - терм; вхождения переменных в термы называются аргументами этого оператора;

4. условный оператор (тест) - логическое выражение; вхождения переменных в логическое выражение называются аргументами этого оператора;

5. оператор петли - односимвольное слово loop.

Среди операторов присваивания выделим случаи: когда τ - переменная, то оператор называется пересылкой (х:=у) и когда τ - константа, то оператор называется засылкой (х:=а).

Подклассы используют ограниченные базисы. Так, например, подкласс V ₁ имеет базис: { х₁, х₂ }, { а, f ⁽¹⁾}, { p ⁽¹⁾},{ start, stop, (,),:=,,} и множество операторов { start (х₁, х₂); х₁:=f (x₁), x₂:=f (x₂), x₁:=а, х₂:= а, р (х₁), р (х ₂), stop (х₁, х₂)}, т. е. схемы из этого подкласса используют две переменные, константу а, один одноместный функциональный символ, один предикатный символ и операторы указанного вида.

Дата добавления: 2015-12-20; просмотров: 16; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 2 3 4 5 678 9 10 11 Следующая ⇒

Мы поможем в написании ваших работ!