виведення

ланцюжка у мовах, породжених контекстно-вільними

граматики типу 2, тобто контекстно-вільні граматики

виведення

ланцюжка у мовах, породжених

контекстно-залежними граматиками

граматики типу 0, тобто загального виду

якщо в граматиці, яка породжує цю

мову,  

якщо граматика,

яка породжує цю мову, має хоча б одну контекстно - залежну продукцію

якщо

існує принаймні одна контекстно - залежна граматика, яка породжує цю мову

якщо

існує принаймні одна контекстно - вільна граматика, яка породжує цю мову

Не

більше одного нетермінального символу у правій частині

Не

більше одного термінального символу у правій частині

принаймні один нетермінальний елемент у лівій частині

тільки

010101

0001

111

скінченна

непорожня множина неподільних символів

сукупність

цифр та букв

нескінченна

множина неподільних елементів

скінченна

множина букв

Вивід у мовах, породжених граматиками будь-якого типу,

може зображатися графічно з використанням орієнтованих кореневих дерев

Вивід у мовах, породжених контекстно-залежними

граматиками, може зображатися графічно з використанням орієнтованих кореневих

дерев

Існує однозначна відповідність між виведенням слова α у граматиці G  та його деревом виводу

Існує

взаємно однозначна відповідність між лівостороннім виводом слова α  у контекстно-вільній граматиці

Не

більше одного термінального символу

Не

більше одного нетермінального символу

Тільки

Тільки

якщо  вони мають однакову множину термінальних

символів

якщо  вони мають однаковий алфавіт

якщо  вони породжують принаймні один однаковий ланцюжок

якщо  вони породжують одну і ту ж мову

Σ⁺

|Σ|

Σ^Ø

Σ^*

слово

, що не

містить жодного символу

скінченна

непорожня множина неподільних символів

слово

, що

складається з одного елементу

слово

без

змістового навантаження