Бюрократы, editor, Администраторы
422
правки
Изменения
→Теорема про удаление
--<br/>
[[Участник:Kirelagin|Кирилл Елагин]]
== Я по-прежнему недоволен алгоритмом поиска ==
Во-первых, что такое «кратчайшее порождение»? Что это вообще символизирует?
Во-вторых, «по индукционному предположению <…> уже содержится в множестве». Что значит «уже»? Ты работаешь с неким алгоритмом, и «уже» ты можешь использовать со ссылкой на время (например, на количество шагов, сделанных алгоритмом). А у тебя всё доказательство оперирует только множеством правил грамматики, что, очевидно, невозможно, ведь тут именно важна итеративность алгоритма.
В-третьих, необходимо доказать, что в алгоритме всегда есть прогресс, т.е., если в какой-то момент после выполнения шага текущее множество не поменялось, это значит, что ''других эпсилон-порождающих нетерминалов нет'' (и наоборот). Вообще это как-то связано с «во-вторых», вроде бы.
Короче, если тебе интересно моё мнение, то я бы удалил нахрен целиком это доказательство и написал его с нуля, тщательно перед этим подумав.
--<br/>
[[Участник:Kirelagin|Кирилл Елагин]]
== Теорема про удаление ==
«Первое использованное правило должно быть построено по правилу».
Последовательность из терминалов и нетерминалов обозначается греческими буквами из начала алфавита. И называть её ''цепочкой'', вообще-то, слегка некорректно, имхо.
В первом абзаце перехода какая-то херня. Откуда там возьмётся перемежение эпсилон-порождающими нетерминалами? Мы же, вроде как, ещё в G' сидим. Дальше доказательство в эту сторону я читать не стал, потому что, по-моему, это уже не имеет смысла.
Мне кажется, тебе надо определиться, у тебя индукция по длине порождения в G или в G'. По-моему, она у тебя то там, то тут, в зависимости от того, что удобнее. Я не уверен, что длины порождений в этих грамматиках совпадают, а если они и совпадают, то это надо явно указать. В связи с этим доказательство в обратную сторону читать я тоже не стал.
Я очень сильно недоволен. Если будет продолжаться в том же духе, ты эту статью никогда не сдашь.
--<br/>
[[Участник:Kirelagin|Кирилл Елагин]]
: Я беру правило из G' и пытаюсь построить соответсвующие правило в G. w - цепочка(слова, string). Я помню, что для грамматик мы использовали слово цепочка.
:: Да, я умею читать, спасибо. Я спрашиваю, по чему у тебя индукция. Это классно, что ты помнишь про цепочки, но, мне кажется, ты не понял, о чём я говорил. А говорил я о том, что у тебя обозначено буковками X и Y. [[Участник:Kirelagin|Кирилл Елагин]]
