Аннотация:
В работе изучается проблема тотальной выводимости в контекстно-свободных, неукорачивающих и контекстно-зависимых грамматиках. Для фиксированного терминального слова проблема состоит в том, чтобы по грамматике определить, существует ли вывод этого слова, в котором каждое правило используется не менее некоторого заданного числа раз. Доказывается, что проблема тотальной выводимости пустого слова в контекстно-свободной грамматике является NP-полной. Для неукорачивающих и контекстно-зависимых грамматик она разрешима за полиномиальное время для слов длины 1 и является NP-полной для любого фиксированного слова длины не менее 2. Аналогичные результаты получены и для варианта проблемы тотальной выводимости с нижним ограничением на число использований нетерминалов в выводе.
