Методичні вказівки до виконання контрольної роботи з дисципліни “Теорія програмування”, страница 4

Відповідно по символу b з підмножини A можна перейти до підмножини {5}, замиканням якої буде підмножина {1,2,4,5,6,7}. Позначимо це замикання буквою С.

Далі виконуємо ті самі переходи вже для підмножин B і C. Процес завершується, коли будуть вичерпані всі підмножини.

Результуюча таблиця переходів для даної схеми буде мати вигляд

Відповідна діаграма переходів має вигляд

Завдання 4 Побудувати контекстно-вільну граматику, що генерує множину ланцюжків { 0ⁿ1ⁿ  | n ≥ 1}.

Граматика визначається як четвірка компонентів  (V_T, V_N, P, S).

            Тут:

V_T  – алфавіт термінальних символів або терміналів;

V_N  – алфавіт нетермінальних символів або нетерміналів, V_T V_N= ;

P  – множина продукцій (або правил) вигляду ,  складається з одного або більше символів V, — з нуля або більше символів V, де V= V_T V_N ;

S   – стартовий символ (або аксіома).

Прикладом контекстно-вільної граматики для даного завдання може бути граматика

( {0, 1}, {S}, P, S )

з набором продукцій:  S –> 01;  S –> 0S1.

Завдання 5 Мовою функціонального програмування описати і застосувати функцію, що обчислює площу круга за відомим діаметром.

Запис даної функції мовою Лісп може мати вигляд

( defun S  ( R ) (*  3.14  R  R) ) ,

а її застосування для радіуса R=5

            (  S  5 ) .

Завдання 6.  Мовою логічного програмування написати програму з такими фактами, правилами і цілями:

Факти: трикутник A  має кути – 30, 60, 90,

  трикутник  B  має кути – 20, 80, 80.

Правило: трикутникє рівнобедреним, якщо два його кути однакові.

Ціль: чи є трикутники  A  і B  рівнобедреними ?

Запис правил і фактів мовою Пролог може мати вигляд

predicates

            tre (symbol, integer, integer, integer)

            rb (symbol)

clauses

            tre (a, 30, 60, 90).

            tre (b, 20, 80, 80).

            rb (V) :- tre (V, X, Y, _), X=Y .

            rb (V) :- tre (V, _, Y, Z),  Y=Z .

            rb (V) :- tre (V, X, _, Z), X=Z .

            Цілі записуються у вигляді  rb(a),  rb(b).

Завдання 7 Написати найслабкішу передумову для послідовності операторів

y := x + 9;

                        x := y + 8,

якщо постумовою Q останнього оператора є { x < 1 }.

            Для послідовності операторів

{P1} S1 {P2},

{P2} S2 {P3}

правило виведення буде таким:

.

            Кожний з операторів є оператором присвоювання вигляду х = Е або y = Е, правило виведення  для якого має вигляд відповідно Р=Q_x=E  або Р=Q_y=E. Іншими словами, передумова  Р обчислюється як умова Q , в якій всі  x  або  y заміняють виразом Е.

            Таким   чином,   передумовою   другого   оператора буде

{y<–7}, а першого – {x < –16}. 

СПИСОК ЛІТЕРАТУРИ

Основна література

1     Ахо А. и др. Компиляторы. Принципы, технологии, инструменты. – М.: Вильямс, 2001. – 768с.

2     Глушков В.М. и др. Алгебра. Языки. Программирование. – К: Наукова думка, 1989. –376c.

3    Жуков Д. Доказательство правильности программ. – Файл.

4    Люгер Д. Искусственный интеллект. – М.: Вильямс, 2003. – 864с

5     Себеста М. Основные концепции языков программирования. – М.: Вильямс, 2001. – 672с.

6     Хантер Р. Основные концепции компиляторов. – М.: Вильямс,2002. – 256с.

7     Хопкрофт Д. и др. Введение в теорию автоматов языков и вычислений. – М.: Вильямс, 2002. – 528с.

Додаткова література

8      Грис Д. Наука программирования. – М.: Мир, 1984

9      Дейкстра Э. Дисциплина программирования. – М.: Мир,

     1978.    

Електронні видання

10       Конспект лекцій дистанційного курсу з  дисципліни “Теорія програмування”.