Варіант 5

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

Обчислити x^y (x, y – додатні цілі числа).

2. Для граматики G=({S, Q, Z, M}, {a, b, c, k}, P, S), де P={S MQa, S , MZcSk, Zab, Sk, Q c, QaaSMc, Mck} вибрати довільний ланцюжок і побудувати відповідне дерево виводу.

3. Виконайте еквівалентні перетворення граматики G= ({S, A, B, C, D}, {a, b, c, d}, P, S), де P = { S→acA | acB |ε, A→ Aa | Ab | a, B→ Cb | ε, C→ dCc, D→ dc} спрямовані на видалення:

1. ε –правил;

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

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

4. Побудуйте, якщо це можливо, контекстно-вільну граматику, яка породжує контекстно-вільну мову L(G) = { cωc | ω ϵ {a, b, c}}, у якій дві літери "a" не стоять поруч.

Варіант 6

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

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

2. Для граматики G=({S, D, R, N}, {a, b, @}, P, S), де P={ S RNS@, S, RDaS, DaNb@, Nb@, NDR, Db} вибрати довільний ланцюжок і побудувати відповідне дерево виводу.

3. Виконайте еквівалентні перетворення граматики G= ({S, R, F, T, E}, {{,}, [, ], a, k, ☺,b}, P, S), де P = { S→ { R | [ R ε, R→ Ra} | Ra ] | a | T | F | ε, F→ {F} | bb, T→ [T], E→ k☺} спрямовані на видалення:

1. ε –правил;

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

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

4. Побудуйте, якщо це можливо, контекстно-вільну граматику, яка породжує контекстно-вільну мову L(G) = { @ω.α | ω ϵ (a, b, … , z), α ϵ (en, ua, ru)}.

Варіант 7

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

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

2. Для граматики G=({S, M, N}, {a, m, n}, P, S), де P={SMaN, S, MaNmS, NaSn} вибрати довільний ланцюжок і побудувати відповідне дерево виводу.

3. Виконайте еквівалентні перетворення граматики G= ({S, L, M, N, R}, {@, n, m, l, ☺,}, P, S), де P = { S→@nL | R, L→M | Ll☺ | Lm☺| ε, M→L | Mm | mm, N→ pN@ | @, R→ nmR} спрямовані на видалення:

1. ε –правил;

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

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

4. Побудуйте, якщо це можливо, контекстно-вільну граматику, яка породжує контекстно-вільну мову L(G) = {%| n = 2m}.

Варіант 8

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

Перевірити чи матиме рівняня ax²+bx+c=0 дійсні корені. (a, b, c – цілі числа).

2. Для граматики G=({S, K, M, D}, {a, d, c}, P, S), де P={S KdD, S , KMc, MDa, McS, D} вибрати довільний ланцюжок і побудувати відповідне дерево виводу.

3. Виконайте еквівалентні перетворення граматики G= ({S, A, B, C}, { a, b, c, @}, P, S), де P = {S→aB@Cc | Aa | ε, A→ @c | ε, B→@CA, C→baB} спрямовані на видалення:

1. ε –правил;

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

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

4. Побудуйте, якщо це можливо, граматику, яка породжує контекстно-вільну мову L(G), слова якої починається і закінчується однаковими парними цифрами, парні і непарні цифри чередуються, але після кожної цифри "3" стоїть цифра "7".