Терминальная доходность

В теории формального языка конечная доходность (или граница ) дерева — это последовательность листьев, встречающихся в упорядоченном обходе дерева.

Деревья разбора и/или деревья вывода встречаются при изучении грамматик фразовой структуры, таких как контекстно-свободные грамматики или линейные грамматики . Листья дерева вывода формальной грамматики G — это терминальные символы этой грамматики, а внутренние узлы — нетерминальные или переменные символы. Соответствующую терминальную строку можно прочитать, выполнив упорядоченный обход дерева и записав терминальные символы в том порядке, в котором они встречаются. Результирующая последовательность терминалов представляет собой строку языка L ( G порожденную грамматикой G. ) ,