Как использовать 1-й шаг в нормальной форме Чомского

Question

Я смущен, когда следует использовать 1-й шаг в преобразовании CNF.

первый шаг: ensure s does not appear on rhs, add new S0 if necessary and copy all rules of S

Это мне не ясно, что означает, что приведенное выше утверждение. Я не знаю, когда создавать S0. Некоторые CFG не начинаются с S0, а некоторые начинаются с S0.

Немного помочь здесь bros.

Answer 1

Цель состоит в том, чтобы избежать появления символа начала на rhs i.e в результате производства. Поэтому вы создаете отдельный символ, который становится единственным и единственным символом начала.

Каковы некоторые из примеров CFG, которые кажутся вам неправильными? Они могут не начинать с этого, но символ, с которым они начинают начинать, не должен появляться в результате производства.