Redigerer Chomsky normalform

I [[Formelt språk|formelle språk]] er et [[kontekstfritt språk]] sagt å være på '''chomsky normalform''' om det har følgende produksjonsregler
: ''A'' → ''BC'', &nbsp; eller
: ''A'' → ''a'', &nbsp; eller
: ''S'' → ε
Hvor A, B og C ikke er terminalsymboler og a er et terminalsymbol. S er startsymbolet og ε er den tomme strengen. Hverken B eller C kan være startsymbolet og den tredje produksjonregelen kan bare være med om den tomme strengen er i det gitte kontekstfrie språket. 

Ethvert kontekstfritt språk kan, ved å følge et sett med regler, gjøres om til chomsky normalform, og ethvert språk i chomsky normalform er et kontekstfritt språk.

== Bruksområder ==
Å få et språk på chomsky normalform er ofte brukt som et preprosesseringssteg. Kontekstfrie språk er viktige innenfor [[kompilatorteknikk]] blant annet. Det blir lettere å jobbe med kontekstfrie språk når alle kontekstfrie språk kan omformes til denne formen.  

== Litteratur ==
* {{cite book|authorlink=Michael Sipser|author=Michael Sipser|year=1997|title=Introduction to the Theory of Computation|url=https://archive.org/details/introductiontoth00sips|publisher=PWS Publishing|isbn=0-534-94728-X}} ''(side 98–101 seksjon 2.1: context-free grammars. Side 156.)''

[[Kategori:Formelle språk]]