Визначення

Ланцюжок , для якої називається сентенціальною формою в граматиці G=(VT, VN, P, S).

Висновок ланцюжка з у КС-граматиці G=(VT, VN, P, S), називається правим (правобічним), якщо у цьому висновку кожна чергова сентенціальна форма виходить з попередньої заміною самого правого нетермінала.

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

Наприклад: для ланцюжка a+b+c у граматиці

G=({a,b},{S,T}, {ST½T+S; Ta½b},S) можна побудувати висновки:

1) ST+ST+T+ST+T+Ta+T+Ta+b+Ta+b+a

2) ST+Sa+Sa+T+Sa+b+Sa+b+Ta+b+a

3) ST+ST+T+ST+T+TT+T+aT+b+aa+b+a

Тут 2 – лівосторонній висновок, 3 – правобічний, а 1 не є ні лівостороннім, ні правобічним, але всі ці висновки є еквівалентними в зазначеному вищі розумінні.

Для КВ-граматик можна ввести зручне графічне представлення висновку, назване деревом висновку, причому для всіх еквівалентних висновків дерева висновки збігаються.

Дерево називається деревом висновку (чи деревом розбору) у КВ-граматиці G=(VT, VN, P, S), якщо виконані наступні умови:

1) кожна вершина дерева позначена символом з множини , при цьому корінь дерева позначений символом S; гілки – символами з ;

2) якщо вершина дерева позначена символом , а її безпосередні нащадки – символами a₁, … a_n, де кожне , то – правило висновку у цій граматиці;

3) якщо вершина дерева позначена символом , а її єдиний безпосередній нащадок позначений символом , то – правило у цій граматиці.

Приклад дерева висновку для ланцюжка a+b+a у граматиці G показано на рис.3.1.