Версия для печати темы

Автор: Виталий`Сергеевич 5.04.2006 13:08

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

Автор: APAL 5.04.2006 14:49

А теперь на "нормальном русском" условие напишите.
Я лингво-грамматический факультет не заканчивал...

Автор: Виталий`Сергеевич 5.04.2006 16:03

А в чем собственно загвоздка ?

Автор: мисс_граффити 5.04.2006 16:13

задание хотя бы сформулируйте более.... эээ... технически.
а по-хорошему, напишите, что пытались делать.

Автор: GoodWind 5.04.2006 16:17

по русски это звучит как "предложения" ? или как "последовательность слов"...

что такое "нетерминал" ?

а это что такое?

Автор: volvo 5.04.2006 16:21

Ну, допустим, задачка-то скопирована... Copy/Paste рулит. Предположим, отсюда:
http://pco.iis.nsk.su/ICP/Practice/dd8-5/node3.html (Задача №19)... А вот объяснения там нет, поэтому и автор вопроса объяснить затрудняется...

P.S. Вот тут:
http://pco.iis.nsk.su/ICP/Practice/dd8-1/node3.html
есть "словарь" понятий, используемый в заданиях...

Автор: APAL 5.04.2006 16:23

- и это тоже хорошо бы пояснить.

Автор: GoodWind 5.04.2006 16:43

APAL, все просто:

надо внимательнее читать задание
т.е. я понимаю так - берем из "вывода" слово, считаем его активную емкость, если она меньше текущей минимальной активной емкости, то сохраняем слово и его активную емкость

Автор: APAL 5.04.2006 17:19

Да, точно! Пока дочитаешь до конца теряется смысл начала...

У меня есть подозрение, что автор темы, выложив сюда задачу, просто хотел пошутить!?

Автор: GoodWind 5.04.2006 18:19

если сегодня автор не появится и не объяснит что ему собстно нужно, закроем тему...

Автор: Виталий`Сергеевич 8.04.2006 12:45

Не пошутил А сам смысл задачи мне самому не сильно понятен, я сюда и написал с целью разобраться!! И я кстати ее не копировал, а списал с учебника, даже и не знал что есть электронный вариант!!!! Все серьезно;) Помогите пожалуйста если сможете

Автор: hardcase 8.04.2006 15:43

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

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

Автор: Виталий`Сергеевич 10.04.2006 21:02

как все плохо то Люди помогайте !!!! Пожалуста !!!!

Автор: Виталий`Сергеевич 11.04.2006 15:01

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

Автор: GoodWind 11.04.2006 16:19

ни как =) я в грамматиках не шарю...

Автор: hardcase 11.04.2006 22:12

Полагаю, это устная задача. И принципиальное решение её я уже привёл выше. Если бы это была задача на программирование, то задача не стояла бы так широко.

Автор: asVitaly 3.05.2006 21:20

Да твое принципиальное решение верно, и задача действительно такая широкая, есть у кого нибудь идеи этой минимизации ? Ведь полный перебор использовать здесь глупо!

Автор: hardcase 4.05.2006 1:30

Согласен. Но мочему-то другого способа не видно.
Правда нужно использовать выводы, которые по возможности не удлинняют цепочку нетерминалов и в тоже время не приводят в левой рекурсии.

Автор: asVitaly 9.05.2006 13:24

есть еще у кого идеи?