Postać normalna Chomsky'ego
Z Wikipedii
Postać normalna Chomsky'ego to postać gramatyki bezkontekstowej, w której wszystkie reguły (inaczej: produkcje) są postaci:
gdzie małe litery oznaczają symbole terminalne, duże zaś nieterminalne.
Każdą gramatykę bezkontekstową nie generują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łki:
(S – symbol startowy, ε – słowo puste), ale gramatyka zawierająca taką regułkę nie może zawierać S po prawej stronie żadnej regułki.
Gramatyka taka to de facto alternatywą gramatyki w postaci normalnej oraz gramatyki generującej tylko symbol pusty.
Zobacz też: postać normalna Greibach, algorytm CYK.
