Eliminacja reguł łańcuchowych Reguły łańcuchowe mają postać gdzie i to symbole nieterminalne. Do każdego symbolu dodajemy produkcję jeśli nie składa się tylko z jednego symbolu nieterminalnego oraz jeśli dana gramatyka zawiera produkcję postaci W przypadku powyższej gramatyki eliminacja reguł łańcuchowych dotyczy tylko jednej produkcji: Po usunięciu tej produkcji gramatyka będzie miała postać:
Eliminacja reguł, w których po prawej stronie stoją więcej niż 2 symbole nieterminalne We wszystkich produkcjach tego typu, czyli o postaci wprowadzamy nowe symbole nieterminalne, które nie są elementami zbioru symboli nieterminalnych danej gramatyki, w poniższy sposób:
W powyższej przykładowej gramatyce eliminacji muszą podlec reguły
W tym celu wprowadzamy nowe symbole nieterminalne
Po pierwszej turze eliminacji gramatyka zawiera jednak jedną produkcję, gdzie po prawej stronie występują więcej niż 2 symbole nieterminalne: By ją znormalizować, wprowadzamy kolejny symbol,
Po tym kroku gramatyka znajduje się w postaci normalnej Chomskiego:
Zobacz też algorytm CYK postać normalna Greibach
Przypisy
Bibliografia
Kategoria:Języki formalne Kategoria:Gramatyka generatywna