Chomskyjev normalni oblik
U računarstvu, formalna gramatika je u Chomskyjevom normalnom obliku ako i samo ako ima sve produkcije u obliku: A → BC or A → α or S → ε gdje su A, B i C nezavršni znakovi, α je završni znak (znak koji predstavlja konstantnu vrijednost), S je početni znak i ε je prazni niz. Također, ni B niti C ne smiju biti početni znakovi. Chomskyjev normalni oblik je imenovan po Noamu Chomskyu, američkom lingvistu, tvorcu Chomskyjeve hijerarhije. Svaka gramatika u Chomskyjevom normalno obliku je kontekstno nezavisna, te prema tome, svaka kontekstno nezavisna gramatika se može svesti na istovjetnu gramatiku u Chomskyjevom normalnom obliku. Sa iznimkom opcionalnog pravila S → ε (uključenog kad gramatika može generisati prazni niz), sva pravila gramatika u Chomskyjevom normalnom obliku su strogo ekspanzivna - prilikom prijelaza između međunizova za vrijeme generisanja niza znakova, svaki međuniz završnih i nezavršnih znakova je uvijek ili iste dužine ili za jedan element veći od prethodnog međuniza. Generisanje niza znakova dužine n se uvijek obavlja u 2n-1 koraka. Štaviše, budući da sve produkcije koje stvaraju nezavršne znakove transformišu jedan nezavršni znak u tačno dva nezavršna znaka, stablo parsiranja gramatike u Chomskyjevom normalnom obliku jest binarno stablo, a dubina ovog stabla ima gornju granicu jednaku dužini niza. Zbog ovih svojstava, mnogi dokazi u području formalnih jezika i izračunjljivosti koriste Chomskyjev normalni oblik. Ova svojstva mogu dovesti do raznih algoritama baziranih na gramatikama u Chomskyjevom normalnom obliku; npr. CYK algoritam koji odlučuje generiše li data gramatika dati niz znakova koristi Chomskyjev normalni oblik.