Задача на грамматики, помогите решить задачу Опции

[Виталий`Сергеевич]

Активной емкостью некоторого вывода в грамматике назовем максимум числа нетерминалов, встречающихся в каждом из промежуточных слов этого вывода
По заданным удлиняющей грамматике и слову найти вывод этого слова с минимальной активной емкостью!
Зараннее благодарен

[hardcase]

Задача странная какая-то.
Получается, у нас есть грамматика Г и в ней есть куча правил, причём если использовать, допустим, цепочку правил А(Г), то через Р шагов мы придём к цепочке терминальных символов, а если использовать правило Б(Г), то мы придём к точно такойже цепочке темриналов но за К шагов, причём К <> Р, и след-но, актиная емкость будет различаться. ЗначиЦа нам нужно для предложенного ввода найти самую короткую цепочку вывода; в случае, когда К < Р это й цепочной будет, вероятно, Б(Г), и А(Г) в противном случае.....

Да, недольшая поправка: вывод не обязательно должен быть самым коротким, он должен включать в минимальное количество нетерминалов.

Сообщение отредактировано: hardcase - 8.04.2006 12:09