Почему мы добавляем новое начальное состояние S0 -> S, когда хотим преобразовать грамматику в нормальную форму Хомского? Что не так, если мы этого не сделаем?Хомский алгоритм преобразования нормальной формы
Сначала я думал, что это из-за правил epsilon. Но мы не удаляем правило epsilon из стартовой переменной. Итак, что выгодно для добавления S0 -> S?
Thanks
В зависимости от того, существует ли пустая строка на языке, у вас может быть правило $ S -> \ epsilon $ (или $ S_0 -> \ epsilon $). Это может удалить произвольное количество символов $ S $, если они могут появиться в правой части правил. Поскольку мы не хотим, чтобы символ начала отображался снова, мы вводим новый.
Таким образом, мы получаем ровно еще один символ для применения правила A -> BC.
Я думаю, у меня есть некоторые объяснения. Если грамматика такова:
S --> S1
S1 --> S
S1 --> a
Затем, на стадии удаления «правил единицы», так как мы не рассматриваем какой-либо определенный порядок, мы можем удалить S -> S1 первого и мы будем иметь:
S1 --> S1
S1 --> a
и начальная переменная полностью удалена.
Я не думаю, что это создает проблему, потому что даже если у вас есть правило S ---> \ epsilon, вы не удалите его, поскольку правило epsilon будет удалено, только если его переменная не является символом начала. –
Дело в том, что с CNF вы знаете, что вывод строки длины n имеет n-1 правил A-> BC и n формы A-> a. Грамматика S-> A, A-> AS, A-> a, S-> eps могла бы выводить строку a сколь угодно большим числом способов. Это не то, что вы хотите от ** нормальной формы **. –