Postać normalna Chomsky'ego
Postać normalna Chomsky'ego to postać gramatyki bezkontekstowej w której wszystkie reguły (inaczej: produkcje) logika .php'>są postaci:gdzie małe litery oznaczają symbole terminalne, duże zaś nieterminalne.Każdą gramatykę bezkontekstową niegenerującą symbolu pustego można przekształcić do postaci normalnej Chomsky'ego Żeby rozszerzyć ten zbiór do wszystkich gramatyk bezkontekstowych rozszerza się czasem postać normalną Chomsky'ego o reguły:Gramatyka taka to de facto alternatywa gramatyki w postaci normalnej oraz gramatyki generującej tylko symbol pusty.Wszystkie symbole terminalne z alfabetu gramatyki zastępujemy symbolami nieterminalnymi, które nie logika .php'>są jeszcze elementami danej gramatyki. Następnie dodajemy produkcje posiadające te nowo wprowadzone symbole po lewej stronie, a po logika .php'>prawej stronie symbole terminalne, które zostały przez nie zastąpione.Przykładowo, poniższa gramatyka bezkontekstowa:poprzez zastosowanie odpowiednich zastąpień zostaje przetransformowana do formy:Reguły łańcuchowe mają postać , gdzie A i B to symbole nieterminalne. Do każdego symbolu A 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ć:We wszystkich produkcjach tego typu, czyli o postaci , wprowadzamy nowe symbole nieterminalne, które nie logika .php'>są elementami zbioru symboli nieterminalnych danej gramatyki, w poniższy sposób:W powyższej przykładowej gramatyce eliminacji muszą podlec regułyW tym celu wprowadzamy nowe symbole nieterminalne B,C:Po pierwszej turze eliminacji gramatyka zawiera jednak jedną produkcję, gdzie po logika .php'>prawej stronie występują więcej niż 2 symbole nieterminalne: . By ją znormalizować wprowadzamy kolejny symbol D:Po tym kroku gramatyka znajduje się w postaci normalnej Chomsky'ego: