0-дуга - до вершини з міткою L0, то цьому розпізнавачів відповідає інструкція
L: if р (? 1, ... ? k) then L1 else L0;
5. якщо вершина з міткою L - петля, то їй відповідає інструкція
L: loop.
Графова форма стандартної схеми
Уявімо стандартну схему програм як розмічений граф, вершинам якого приписані оператори з деякого базису В.
Стандартної схемою в базисі В називається кінцевий (розмічений орієнтований) граф без вільних дуг і з вершинами наступних п'яти видів:
. Початкова вершина (рівно одна) позначена початковим о1ператором. З неї виходить рівно одна дуга. Немає дуг, ведуть до початкової вершини.
. Заключна вершина (може бути декілька). Позначена заключним оператором. З неї не виходить жодної дуги.
. Вершина-перетворювач. Позначена оператором присвоювання. З неї виходить рівно одна дуга.
. Вершина-распознаватель. Позначена умовним оператором (званим умовою даної вершини). З неї виходить рівно дві дуги, помічені 1 (ліва) і 0 (права).
. Вершина-петля. Позначена оператором петлі. З неї не виходить жодної дуги.
Кінцеве безліч змінних схеми S складають її пам'ять ХS.
З визначення випливає, що один і той же оператор може позначати кілька вершин схеми.
Вершини іменуються (мітки вершини) цілим невід'ємним числом (0, 1, 2 ...). Початкова вершина завжди позначається міткою 0. p align="justify"> Схема S називається правильною, якщо на кожній дузі задані всі змінні.
Інтерпретація стандартних схем програм
ССП не є записом алгоритму, тому дозволяє досліджувати тільки структурні властивості програм, але не семантику обчислень. При побудові В«семантичноїВ» теорії схем програм вводиться поняття інтерпретація ССП. Визначимо це поняття. p align="justify"> Нехай в деякому базисі У визначений клас ССП. Інтерпретацією базису У в області інтерпретації D називається функція I, яка зіставляє:
1. кожної змінної х з базису В - деякий елемент d = I (x) з області інтерпретації D;
2. кожній константі а з базису В - деякий елемент d = I (а) з області інтерпретації D;
. кожному функціональному символу f (n) - усюди певну функцію F (n) = I (f (n));
