Вправи Д/З

1) Нехай – породжуюча граматика, де , ,

Виписати термінальні ланцюжки, що породжуються даною граматикою, та визначити довжину їхнього виводу.

2) Нехай , де , ,

Визначити термінальні ланцюжки, що породжуються даною граматикою, і довжину їхнього виводу.

3) Для граматики G відомі її загальний словник {A, B, C, D, E} та схема правил . Визначити склад термінального і нетермінального словників, ціль граматики, побудувати мову L(G), визначити довжину виводів для кожного термінального ланцюжка.

4) Визначити, чи породжуючими наступні граматики:

a) ;

b) ;

5) Дано граматику , где , , . Визначити чи належить ланцюжок ABABBABB множині L(G).

6.2 Методичні вказівки по організації самостійної роботи студентів

6.3 Контрольні питання і завдання

6.4 Приклади аудиторних і домашніх задач

Тема 7. Породжуючі граматики. Побудова ФГ, що породжує формальну мову із заданими властивостями. Визначення типу граматики (два заняття)

7.1 Мета занять

Вивчити основні типи породних граматик за ієрархією Н. Хомського, отримати практичні навички побудови ФГ, що породжує формальну мову із заданими властивостями, навчитися визначати тип породної граматики, аналізуючи схему граматики.

7.2 Методичні вказівки з організації самостійної роботи студентів

При вивченні даної теми необхідно

Граматики типу 2 (КВ-граматики) найбільш широко використовуються в різних лінгвістичних моделях, які знаходять різноманітне застосування. Продукції таких граматик мають вигляд:

A→β, де A є VN, β є (VT U V­N)+

Формальна мова L(G), що породжується граматикою G, називається термінальною, якщо L – множина термінальнихланцюжків граматики G3, які виводяться з початкового символу S за правилами граматики Р:

Конструктивний опис формальних мов здійснюється за допомогою формальних систем спеціального виду формальних породних граматик.

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

Зокрема, нерозв'язна проблема розпізнавання еквівалентності двох граматик (розв'язний лише її окремий випадок, коли обидві граматики мають тип 3).

7.3 Контрольні запитання і завдання

1. Які формальні граматики називаються породними?

2. Наведіть класифікацію породжуючих граматик за ієрархією Н. Хомського.

7.4 Приклади аудиторних і домашніх задач

Приклад 1:

Множина непарних чисел в унарному представленні – це множина ланцюжків виду а, ааа, ааааа, …, тобто мова {a^2n-1}(n=1,…). Вона породжується граматикою G = <V_T, V_n, P, S>, де V_T={a}, V_N={S}, Р містить правила:

Р={S→a; S → aaS}

З виду правил безпосередньо випливає, що мова має тип 3.

Приклад 2:

Мова (G)={aⁿbⁿ} є КВ-мовою (типа2), оскільки вона породжується КВ-граматикою G = <V_T, V_n, P, S>, V_T={a, b}, V_N={S} з двома правилами виводу:

Р={S→aSb, S→ab}

Приклад 3:

Мова булевих формул зі змінними a, b, c породжується КВ-граматикою, де

V_T={a, b, c, V, &, ┐, (,)}; V_N={S},

P={S→(SVS); S→ (S/\S); S→┐; S→a; S→b; S→c }

Ця мова відрізняється від мови формул числення висловлень відсутністю імплікації.

Приклад 4:

Якщо в попередній мові останні три правила, що вводять операції V, &, T замінити чотирма правилами, що вводять операції +, -, *, /, то одержимо мову арифметичних виразів.

Ця мова відрізняється від звичайної мови арифметичних виразів тим, що не враховує асоціативності додавання та множення, а також пріоритетів операцій, і тому її вирази містять занадто багато дужок (аналогічне зауваження ставиться до попереднього приклада).

Більш близька до звичайної мова арифметичних виразів зі змінними a, b, c задається більш складною КВ-граматикою:

1. S→T;

2. S→ S + T

3. S→ S - T

4. T → M

5. T → T*M

6. T → T/M

7. M → (S)

8. M → K

9. K → a

10. K →b

11. K → c

Для повного співпадання зі звичайною мовою арифметичних виразів у цю граматику треба додати правила, що породжують числові константи та довільні ідентифікатори змінних (?)

(Для сам./р.)

Приклад 5:

Мова {aⁿbⁿaⁿ} породжується наступною граматикою:

S → aBa;

B → aBCa;

B → b;

BC → bB; bC →bB

aC → Ca.

Ця граматика не є контекстною через останні два правила. Однак, можна переконатися, що їй еквівалентна наступна контекстна граматика:

P = {S → ABA;

B → ABCA;

B → b;

bC → bb;

AC → DC

DC →DA

DA →CA

A →a}

у якій неконтекстне правило аС →Са замінено чотирма контекстними правилами, а А відіграє роль двійника а.

Тому мова {aⁿbⁿaⁿ} має тип 1.

Приклад 6:

Для граматики G₁ = (V_T,V_N, P, S), VN={S}, P1={S → B, S → CS} рядки породженої нею мови утворюють нескінченну множину:

L(G1) = {B, CB, CCB, CCCB, …}

Приклад 7:

Побудувати граматику G₂, що породжує мову L(G₂)={aⁿb^m | n, m = 1, 2, …}

У цьому випадку всі ланцюжки мови α є L(G₂) можна розглядати як результат конкатенації α є βγ, де β = aⁿ, γ = a^ь. Для ланцюжків β і γ можна побудувати правила граматики, використовуючи поняття рекурсії та вводячи необхідну кількість нетермінальних символів. Отримуємо:

P₂ = { S → BC, B →a, B →ab, C →b, C →bc}

S →AB, A →a, A →aA, B →b, B →bB

Приклад 8:

Побудувати граматику, що породжує ланцюжки

{GET_EDIT, PUT_EDIT}.

Кожний такий ланцюжок можна представити, як складений із трьох частин: α = βγδ, де β приймає значення GET чи PUT, γ – являє собою довільну кількість пропусків (не менше одного), δ є константою EDIT. Виходячи з цього, одержуємо наступні правила:

Р₃ = {S →BC EDIT, B →PUT, B →GET, C →_C, C →_}

Приклад 9:

Нехай потрібно побудувати мову для опису рівносторонніх трикутників, у яких кожна зі сторін складається з кінцевого числа орієнтованих відрізків визначеної довжини. На рис. 6.1 наведені приклади таких трикутників.

Рисунок 7.1 –. Графічна інтерпретація формальної мови {lⁿ, rⁿ, xⁿ} (а)

та її термінальних символів (б)

В залежності від напряму позначимо ці відрізки символами l, r чи x (як показано на рис. 7.1). Рухаючись за годинною стрілкою від лівого нижнього кута кожного трикутника, отримаємо наступні описи цих трикутників:

LLLRRRXXX,

LLRRXX,

LLLLRRRRXXXX.

Можна вважати, що це ланцюжки деякої мови опису рівносторонніх трикутників вказаного типу:

Для даної мови можна запропонувати наступну граматику типу 1, яку, однак, не можна віднести до класу безконтекстних граматик:

G = (V_T, V_N­, P, S)

де V_T = {l, r, x}, V_N = {S, R, X}, а множина продукцій P:

P = { (1) S→lSRX,

(2) S→lRX,

(3) XR→RX,

(4) lR→lr,

(5) rR→rr,

(6) rX→rx,

(7) xX→xx }

Щоб отримати ланцюжок lⁿrⁿxⁿ, потрібно зробити наступну кількість кроків:

,

причому першу продукцію необхідно застосувати (n-1) раз, потім один раз другу продукцію, 1/2n(n-1) раз – третю, один раз - четверту, n-1 раз – п’яту, один раз – шосту, n(n-1) раз – сьому. Можна довести, що за допомогою даної граматики не можна побудувати термінальні ланцюжки, які не є ланцюжками мови { ln, rn, xn }. Більше того, можна довести, що даній мові не може відповідати ніяка безконтактна граматика.