Упражнения к Лекции 5.

5.1. Функции

function F(x, y: integer): integer;

function G(x, y: integer): integer;

function R(x, y: integer): integer;

определены с помощью операционной семантики равенствами:

R(x, y) = x*(y – 1),

F(x, y) = R(x + 1, y) - R(x, y - 1),

G(x, y) = F(x, R(x, y)).

Найти значения G(3, 3).

5.2. Функции

function F(n: integer): integer;

function G(n: integer): integer;

определены с помощью операционной семантики равенствами:

F(0)=1,

G(0)=2,

F(n)=G(n-1),

G(n)=F(n-1) + G(n-1).

Найти значения F(3) и G(3).

5.3. Формальные языки E и T определены над алфавитом

{'a', '*', '&', '<', '>'}

с помощью денотационной семантики равенствами

E= T U '*' T U E '&' T,

T= 'a' U 'a*' U '<' E '>'

Какие из следующих строк

'*a&*a*&a*',

'*a&<a&a*>',

'*<*a*&a>&<*a*>*'

принадлежат языку E и какие из них не принадлежат языку E.

5.4. Тип R определён с помощью следующей аксиоматической семантики.

Описания:

type R= record P1, P2, P3: CHAR end;

function READ(S: R): CHAR; {READ: R ® CHAR}

function SHIFT(S: R): R; {SHIFT: R ® R}

function ADD(S: R, C: CHAR): R; {ADD: R * CHAR ® R}

function REMOVE(S: R): R; {REMOVE: R ® R}

var X, Y, Z: CHAR;

U: R;

Аксиомы:

SHIFT(ADD(ADD(ADD(U, X), Y), Z)) =

ADD(ADD(ADD(U,Y), Z), X);

REMOVE(U) = SHIFT(ADD(U, '#'));

READ(SHIFT(ADD(U, X))) = X;

Найти значение:

READ(SHIFT(SHIFT(REMOVE(ADD(ADD(U, 'a'), 'b'))))) =

Литература к Лекции 5.

2.1. В.Н. Агафонов. Спецификация программ: понятийные средства и их организация. - Новосибирск: Наука (Сибирское отделение), 1987.

2.2. Ian Sommerville. Software Engineering. - Addison-Wesley Publishing Company, 1992.

2.3. Д. Скотт. Теория решеток, типы данных и семантика / Данные в языках программирования. - М.: Мир, 1982. - С. 25-53.

2.4. К. Хоор. О структурной организации данных / У. Дал, Э. Дейкстра, К. Хоор. Структурное программирование. - М.: Мир, 1975. -

С. 98-197.

Разделяй и властвуй!

Римская пословица

Лекция 6.

Не нашли, что искали? Воспользуйтесь поиском: