Алгоритм преобразования нормальных форм Хомского

Question

Почему мы добавляем новое начальное состояние S0 -> S, когда хотим преобразовать грамматику в нормальную форму Хомского? Что пойдет не так, если мы этого не сделаем?

Сначала я думал, что это из-за правил эпсилон. Но мы не удаляем эпсилон-правило из стартовой переменной. Так в чем же преимущество добавления S0 -> S?

Спасибо

Answer 1

В зависимости от того, есть ли на языке пустая строка, у вас может быть правило $S -> \epsilon$ (или $S_0 -> \epsilon$). Это может удалить произвольное количество символов $S$, если они могут появиться в правой части правил. Поскольку мы не хотим, чтобы начальный символ появлялся снова, мы вводим новый.

Таким образом, мы получаем ровно еще один символ на каждое применение правила A -> BC.

Answer 2

Я думаю, у меня есть какое-то объяснение. Если грамматика такая:

S --> S1
S1 --> S
S1 --> a

Затем, на этапе удаления "правил модуля", поскольку мы не рассматриваем какой-либо конкретный порядок, мы можем сначала удалить S -> S1, и у нас будет:

S1 --> S1
S1 --> a

и переменная начала полностью удаляется.