Нормальная форма Хомского, удаляющая эпсилон-переходы

Я работаю над преобразованием 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?


chomsky-normal-form
person Conner R Panarella    schedule 28.10.2014    source источник

Ответы (1)


arrow_upward
-1
arrow_downward

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

person Brian Tompsett - 汤莱恩    schedule 27.05.2015