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

Завдання 2 За регулярним виразом (a|b)^*ab методом Томпсона побудувати ε- недетермінований автомат.

Завдання 3 Методом побудови підмножин перетворити ε- недетермінований автомат із завдання 2 у детермінований автомат. Результатом повинна бути діаграма переходів для відповідного детермінованого автомата.

Завдання 4  Є граматика з продукціями

PROGRAM  ->  begin DECS ; STATS end

DECS -> D ; DECS  | D

STATS          ->  S ; STATS | S  .

Написати ліве породження для

            begin D ; D ; S ; S end

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

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

Факти: a  – позитивне;

            b – негативне.

Правило: добуток xy позитивний, якщо x і y – обоє позитивні або обоє негативні.

Ціль: чи є ab позитивним ?

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

y := 4*x – 5;

                        x :=2* y – 11,

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

Варіант 4

Завдання 1 Написати регулярний вираз для мови, яка представляє собою множину ланцюжків з 0 і 1, що містять не більш однієї пари послідовних нулів.

Завдання 2 За регулярнм виразом (a|b)^*abb методом Томпсона побудувати ε- недетермінований автомат.

Завдання 3 Методом побудови підмножин перетворити ε- недетермінований автомат із завдання 2 у детермінований автомат. Результатом повинна бути діаграма переходів для відповідного детермінованого автомата.

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

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

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

Правило: добуток xy позитивний, якщо x>0, y>0 або  x<0,  y<0.

Ціль: чи є добуток (-1) і (-5) позитивним ?

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

y := 2*x + 1;

                        x := y – 4,

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

Варіант 5

            Завдання 1 Написати регулярний вираз для мови, яка являє собою множину ланцюжків з 0 і 1, у яких число нулів кратне 2.

Завдання 2 За регулярнм виразом (b|c)^* методом Томпсона побудувати ε- недетермінований автомат.

Завдання 3 Методом побудови підмножин перетворити ε- недетермінований автомат із завдання 2 у детермінований автомат. Результатом повинна бути діаграма переходів для відповідного детермінованого автомата.

Завдання 4 Подана граматика породжує мову регулярного вираження { 0*1(0|1)* }:

S –> A1B ,  A –> 0A | ε ,   B –> 0B | 1B | ε.

Записати ліве і праве породження для ланцюжка 00101.

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

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

Факти: a  – поле класу c ;

 b – метод класу d.

Правило: x – є членом класу y, якщо x – поле y або x – метод y.

Ціль: чи є a членом класу d?

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

y :=  4*x – 15;

                        x := y,

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

Варіант 6

            Завдання 1 Написати регулярний вираз для мови, яка являє собою множину ланцюжків з 0 і 1, у яких число нулів кратне 3.

Завдання 2 За регулярним виразом (b|c)^*b методом Томпсона побудувати ε- недетермінований автомат.

Завдання 3 Методом побудови підмножин перетворити ε- недетермінований автомат із завдання 2 у детермінований автомат. Результатом повинна бути діаграма переходів для відповідного детермінованого автомата.

Завдання 4 Подана граматика породжує мову регулярного виразу {0*1(0|1)* }:

S –> A1B ,  A –> 0A | ε ,   B –> 0B | 1B | ε.

Записати ліве і праве породження для ланцюжка 1001.

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

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

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

  трикутник  B  має кути – 45, 45, 90.

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

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

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

y := x + 4;

                        x := y – 4,

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