Chomsky-normaalvorm
Uit Wikipedia, de vrije encyclopedia
Chomsky-normaalvorm is een begrip uit de theoretische informatica, in het bijzonder het gebied der formele talen. De Chomsky-normaalvorm is een kenmerk dat een formele grammatica al dan niet kan bezitten.
De Chomsky-normaalvorm is interessant vanuit het oogpunt van berekenbaarheid; veel bewijzen maken er gebruik van. Daarbij leiden grammatica's in de Chomsky-normaalvorm tot efficiënte algoritmes; een voorbeeld is het CYK-algoritme, dat beslist of een gegeven string gegenereerd kan worden door een gegeven grammatica.
De Chomsky-normaalvorm is genoemd naar Noam Chomsky, de Amerikaanse taalkundige die de Chomskyhiërarchie bedacht.