Chomsky Нормальная форма удаления epsilon переходов

Question

Я работаю над преобразованием CFG в нормальную форму Хомского, но у меня есть некоторые трудности.

У меня есть эта CFG

A-> BAB|B|epsilon B -> 00|epsilon

Хорошо я добавить новое начальное состояние

S -> A A-> BAB|B|epsilon B -> 00|epsilon

Затем я должен удалить эпсилон переходы, так что я начать с B

S -> A A-> BAB|B|AB|BA|A|epsilon B -> 00

Как удалить эпсилон из A? Может ли в начале быть эпсилон? И как мне преобразовать A-> A?

Answer 1

Вы не можете преобразовать эту грамматику в единицу без ε и, следовательно, ее нельзя записать в нормальной форме Хомского. Это связано с тем, что все производственные процессы могут уменьшаться до ε, поэтому ε является допустимым предложением на языке.