Przekształcenie gramatyki do postaci Chomsky'ego - epsilony

[lunex]

Witam,
chciałbym się dowiedzieć w jaki sposób przy przekształcaniu gramatyki do postaci normalnej Chomsky'ego pozbyć się epsilonów. Przykładowo mamy gramatykę:

\(\displaystyle{ S \rightarrow A B \\
A \rightarrow A B S | a a \\
B \rightarrow B A | b b b | \epsilon}\)

i teraz w jaki sposób pozbyć się tego epsilona przy B? Nigdzie nie mogę na to znaleźć dobrze wytłumaczonej odpowiedzi ;/ Z góry dziękuję za pomoc.

[paladin]

Skoro B może zamienić się w słowo puste, możesz uwzględnić ten fakt - dla każdej produkcji, w której występuje B tworzysz nową, z B od razu zamienionym na \(\displaystyle{ \epsilon}\). Na przykład do produkcji \(\displaystyle{ S \rightarrow AB}\) dochodzi jeszcze \(\displaystyle{ S \rightarrow A}\).

[lunex]

ok, piękne dzięki.