Обсуждение:Удаление eps-правил из грамматики

Приведи в порядок списки (они должны быть нормальные, как везде, а не через жопу). Положи на место звёздочки у «выводится». Выдели жирным определяемые термины в определениях. Короче, приведи статью в порядок, а то так это какой-то трэш. Кирилл Елагин

Учёл замечания. Я понял, что к содержанию статьи вопросов нет, так как мы перешли к оформлению?

Это утверждение не верно =). Кирилл Елагин

Много ненависти

Я не очень понял про выход алгоритма удаления. Насколько я понимаю, там написано, что алгоритм выдаёт грамматику, распознающую такой же язык, кроме слова ε. Соответственно, эээ… не понятно, с чего ты решил, что ε пропадает, и не указано то особенное свойство, которым обладает выходная грамматика, ради которого всё и задумано (отсутствие ε-правил). Соответственно, та же хрень с формулировкой теоремы о корректности (так что доказательство я пока не стал читать, ибо читать доказательство теоремы, формулировку которой я понимаю до конца — это странно).

Я плакал кровавыми слезами, когда увидел «[math]A \Rightarrow^* \varepsilon[/math] за один шаг». Мне хотелось взять топор и пойти убивать.

Меня категорически не устраивает оборот «Обозначим X за Y».

А самое грустное в этой истории то, что, на мой взгляд, теорема про поиск нетерминалов доказывает… эээ… судя по всему, она доказывает определение. Подумай об этом, пожалуйста.

Когда в алгоритме поиска объектов, обладающих свойством X, первая строчка выглядит как «Пусть A — множество объектов, обладающих свойством X», это вызывает у меня лёгкое недоумение. Я, конечно, понимаю, «что хотел сказать автор», но… мм… короче, не дело.

--
Кирилл Елагин

Я по-прежнему недоволен алгоритмом поиска

Во-первых, что такое «кратчайшее порождение»? Что это вообще символизирует?

Во-вторых, «по индукционному предположению <…> уже содержится в множестве». Что значит «уже»? Ты работаешь с неким алгоритмом, и «уже» ты можешь использовать со ссылкой на время (например, на количество шагов, сделанных алгоритмом). А у тебя всё доказательство оперирует только множеством правил грамматики, что, очевидно, невозможно, ведь тут именно важна итеративность алгоритма.

В-третьих, необходимо доказать, что в алгоритме всегда есть прогресс, т.е., если в какой-то момент после выполнения шага текущее множество не поменялось, это значит, что других эпсилон-порождающих нетерминалов нет (и наоборот). Вообще это как-то связано с «во-вторых», вроде бы.

Короче, если тебе интересно моё мнение, то я бы удалил нахрен целиком это доказательство и написал его с нуля, тщательно перед этим подумав.

--
Кирилл Елагин

Теорема про удаление

«Первое использованное правило должно быть построено по правилу».

Последовательность из терминалов и нетерминалов обозначается греческими буквами из начала алфавита. И называть её цепочкой, вообще-то, слегка некорректно, имхо.

В первом абзаце перехода какая-то херня. Откуда там возьмётся перемежение эпсилон-порождающими нетерминалами? Мы же, вроде как, ещё в G' сидим. Дальше доказательство в эту сторону я читать не стал, потому что, по-моему, это уже не имеет смысла.

Мне кажется, тебе надо определиться, у тебя индукция по длине порождения в G или в G'. По-моему, она у тебя то там, то тут, в зависимости от того, что удобнее. Я не уверен, что длины порождений в этих грамматиках совпадают, а если они и совпадают, то это надо явно указать. В связи с этим доказательство в обратную сторону читать я тоже не стал.

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

--
Кирилл Елагин

Я беру правило из G' и пытаюсь построить соответсвующие правило в G. w - цепочка(слова, string). Я помню, что для грамматик мы использовали слово цепочка.