Дерево вывода слова

Пусть $G=(\Gamma ,\Sigma ,P,S)$ — КС-грамматика, $S\Rightarrow {\alpha }_1\Rightarrow \dots \Rightarrow {\alpha }_n=w\in {\Sigma }^{\ast }$ - вывод, тогда деревом вывода цепочки $w$ называется корневое дерево, построенное по следующим правилам:

• Корень дерева помечен аксиомой
• Все внутренние узлы дерева помечены нетерминалами, при этом если внутренний узел помечен нетерминалом $A$ и $A\to X_1{X}_2\dots X_s,X_i\in (\Gamma \cup \Sigma {)}^{\ast },i=1\dots s$ — правило вывода, которое было применено в выводе, тогда у этого узла сыновьями будут узлы, помеченные $X_1,X_2,\dots X_s$ в указанном порядке слева направо
• Листья дерева помечены терминалами или $\epsilon$, при этом если узел помечен $\epsilon$, то у него нет братьев

Узлы дерева называются братьями, если имеют одного родителя