Густота – мера сложности вывода в контекстно-свободной грамматике

Получена точная (по порядку) оценка роста сигнализирующей функции густоты для контекстно-свободных грамматик (кс-грамматик), порождающих множество $L_0$ всех правильных бинарных скобочных последовательностей (т.е. а) содержащее последовательность ( ), б) содержащее $(z_1z_2)$ для всяких $z_1,z_2\in L_0$ и в) не содержащее никаких других цепочек).