НОУ ІНТУІТ, Лекція, Слова, мови та граматики

1.5. Класи граматик

Визначення 1.5.1.Контекстною граматикою (контекстно-залежною граматикою, граматикою безпосередньо складових, НС-граматикою, граматикою типу1 , context-sensitive grammar , phrase-structure grammar ) називається граматика, що породжує, кожне правило якої має вигляд , де , .

Приклад 1.5.2. Граматика

Визначення 1.5.3.Контекстно-вільною граматикою(безконтекстною граматикою, КС-граматикою, граматикою типу2, context-free grammar) називається породжувальна граматика, кожне правило якої має вигляд, де,.

Приклад 1.5.4. Граматика

Визначення 1.5.5.Лінійною граматикою(linear grammar ) називається граматика, що породжує, кожне правило якої має вигляд або , де , , , .

Визначення 1.5.7.Праволінійною граматикою(раціональною граматикою, граматикою типу3, right-linear grammar) називається породжувальна граматика, кожне правило якої має вигляд або, де,,.

Приклад 1.5.8. Граматика

Приклад 1.5.9. Граматика

Приклад 1.5.10. Граматика

граматики

Приклад 1.5.11. Граматика

граматики

Визначення 1.5.12. Правила виду називаються -правиламиабоепсілон-правилами.

Лемма 1.5.13.Кожна праволінійна граматика є лінійною. Кожна лінійна граматика є контекстно-вільною. Кожна контекстно-вільна граматика без правил є контекстною граматикою.

Визначення 1.5.14. Класи граматик типу 0, 1, 2 і 3 утворюють ієрархію Хомського ( Chomsky hierarchy ).

Визначення 1.5.15. Мова називаєтьсямовою типу0(контекстною мовою, контекстно-вільною мовою, лінійною мовою, праволінійною мовою), якщо вона породжується деякою граматикою типу 0 (відповідно контекстною граматикою, контекстно-вільною граматикою, лінійною граматикою, праволінійною граматикою). Контекстно-вільні мови називаються також алгебраїчними мовами.

Приклад 1.5.16. Нехай дано довільний алфавіт

Вправа 1.5.17. Якому класу належить граматика

Вправа 1.5.18. Якому класу належить граматика

Вправа 1.5.19. Знайти праволінійну граматику, що породжує мову.

Вправа 1.5.20. Знайти праволінійну граматику, еквівалентну граматиці

Вправа 1.5.21. Знайти праволінійну граматику, еквівалентну граматиці