Chomsky-normaalvorm
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.
Definitie[bewerken | brontekst bewerken]
Een formele grammatica is in Chomsky-normaalvorm als en slechts als alle productieregels in die grammatica van een van de volgende vormen zijn:
- A → BC
- A → α
- S → ε
waar A, B en C niet-terminale symbolen zijn, α een terminaal symbool (een symbool met een constante waarde), S het startsymbool is, en ε de lege string is. Verder mag het startsymbool niet B of C zijn.
Elke grammatica in Chomsky-normaalvorm is contextvrij, en elke contextvrije grammatica kan op een efficiënte manier omgezet worden naar een equivalente grammatica in Chomsky-normaalvorm.
Uitgezonderd de productieregel S → ε (wordt enkel gebruikt als de grammatica de lege string kan genereren), zijn alle productieregels van een grammatica in Chomsky-normaalvorm uitbreidend; dus gedurende de afleiding van een string heeft elke string van terminale symbolen en niet-terminale symbolen dezelfde lengte of juist 1 element meer dan de vorige string. De afleiding van een string van lengte n is altijd precies 2n - 1 stappen lang. En aangezien alle productieregels die niet-terminale symbolen afleiden een niet-terminaal symbool in exact 2 niet-terminale symbolen transformeert, is de syntaxisboom gebaseerd op een grammatica in Chomsky-normaalvorm altijd een binaire boom. De hoogte van deze boom heeft als maximum hoogte de lengte van de string.
Alternatieve definitie[bewerken | brontekst bewerken]
Een aantal bronnen definiëren de Chomsky-normaalvorm op de volgende manier, die licht afwijkt:
Een formele grammatica is in Chomsky-normaalvorm als en slechts als alle productieregels in die grammatica van een van de volgende vormen zijn:
- A → BC
- A → α
waar A, B en C niet-terminale symbolen zijn, en α een terminaal symbool is. Bij definitie mag het startsymbool wel B of C zijn.
Het verschil tussen deze definitie en de vorige is dat een grammatica die aan deze definitie voldoet de lege string niet kan genereren. Dit doet echter geen afbreuk aan het feit dat elke contextvrije grammatica die taal L accepteert, efficiënt omgezet kan worden naar een grammatica in Chomsky-normaalvorm die taal L - {ε} accepteert. Het grootste voordeel van deze definitie is dat bewijzen een beetje gemakkelijker worden, aangezien geen enkele stap in een afleiding de lengte van de resulterende string kan verkleinen. Het nadeel is dan weer dat er maatregelen genomen moeten worden als de originele grammatica ε genereert.
Zie ook[bewerken | brontekst bewerken]
Referenties[bewerken | brontekst bewerken]
- Michael Sipser, Introduction to the Theory of Computation, PWS Publishing. ISBN 0-534-94728-X, 1997.
- John Martin, Introduction to Languages and the Theory of Computation, McGraw Hill, 2003. ISBN 0-07-232200-4.