Варіант 13

1. Побудувати програму на мові SIPL. Перевірити синтаксичну правильність програми , побудувавши її дерево синтаксичного виводу. Побудувати семантичний терм даної програми та застосувати його до певних вхідних даних.

Одноклітинна амеба кожні три години ділиться на 2 частини. Порахувати скільки амеб буде через x годин (x – додатне ціле число).

2. Для граматики G=({S, Q, A, B}, {a, b, c}, P, S), де P={SBA, S , BQb, QAa, Ac} вибрати довільний ланцюжок і побудувати відповідне дерево виводу.

3. Виконайте еквівалентні перетворення граматики G=({R, T, U, W, V}, {0, 1, +, -, *, /}, P, R), де P = {R→T1T | T1U | W | ε; T→U | T01 | T10 | ε; U→+U | +0 | +1, W→W-W | W+W; V→*0 | /1} спрямовані на видалення:

1. ε –правил;

2. Непродуктивних символів;

3. Недосяжних символів.

4. Побудуйте, якщо це можливо, ліволінійну граматику, яка породжує мову L(G) = {aⁿ$b^m| n>0, m>0}.

Варіант 14

1. Побудувати програму на мові SIPL. Перевірити синтаксичну правильність програми , побудувавши її дерево синтаксичного виводу. Побудувати семантичний терм даної програми та застосувати його до певних вхідних даних.

Обчислити x–y (x ≥ y), використовуючи цикл та операцію додавання (x, y – додатні цілі числа).

2. Для граматики G=({S, A, B, C}, {a, b, c}, P, S), де P={S AbC, S , ABc, Bab, C} вибрати довільний ланцюжок і побудувати відповідне дерево виводу.

3. Виконайте еквівалентні перетворення граматики G=({Q, A, B, C, D}, {0, 1, -}, P, Q), де P = {Q→01A | 01B | A; A→ 0B1 | B | 1 | ε; B→BA0 | B1 | C | ε; C→0C11; D→ - D1 | -0 | -1} спрямовані на видалення:

1. ε –правил;

2. Непродуктивних символів;

3. Недосяжних символів.

4. Побудуйте, якщо це можливо, ліволінійну граматику, яка породжує мову L(G) = {(01)ⁿ⊥| n>0}.

Варіант 15

1. Побудувати програму на мові SIPL. Перевірити синтаксичну правильність програми , побудувавши її дерево синтаксичного виводу. Побудувати семантичний терм даної програми та застосувати його до певних вхідних даних.

Визначити чи є число x дільником числа y (x, y – додатні цілі числа).

2. Для граматики G=({S, A, B, D}, {a, b, c}, P, S), де P={S AcB, Abc, BacD, Dabc} вибрати довільний ланцюжок і побудувати відповідне дерево виводу.

3. Виконайте еквівалентні перетворення граматики G=({X, Y, Z, K, L}, {a, b, l, =, <, >, ∧, ∨, ¬}, V, X), де V = {X→Y | Y=Y | Y<Y | Y>Y | K; Y→Y∧Z | Y∨ Z | ε; Z→ ¬ a | ¬ b| ε; K→ ¬ K; 5) L→ l | a | b} спрямовані на видалення:

1. ε –правил;

2. Непродуктивних символів;

3. Недосяжних символів.

4. Побудуйте, якщо це можливо, ліволінійну граматику, яка породжує мову L(G) = {(ab)ⁿ(cd)^m | n>0, m>0}.

Варіант 16

1. Побудувати програму на мові SIPL. Перевірити синтаксичну правильність програми , побудувавши її дерево синтаксичного виводу. Побудувати семантичний терм даної програми та застосувати його до певних вхідних даних.

Обчислити суму парних чисел на проміжку [0, x] (x – додатне ціле число)

2. Для граматики G=({S, A, B, С}, {b, c, v}, P, S), де P={SSBC, S , BAb, Acv, Cc} вибрати довільний ланцюжок і побудувати відповідне дерево виводу.

3. Виконайте еквівалентні перетворення граматики G=({S, X, Y, Z, K}, {x, y, z, k, #, $}, P, S), де P = { S→X | Y | Z; X→x#X | x#Y | ε; Y→Yy$ |Yz$ | $ | ε; Z→Zz$; K→Kk$ | k$} спрямовані на видалення:

1. ε –правил;

2. Непродуктивних символів;

3. Недосяжних символів.

4. Побудуйте, якщо це можливо, ліволінійну граматику, яка породжує мову L(G) = {(abc)^m , ε | m≥0}.