Chomsky normalform

I formelle språk er et kontekstfritt språk sagt å være på chomsky normalform om det har følgende produksjonsregler
 A → BC,   eller
 A → a,   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 
  (side 98–101 seksjon 2.1: context-free grammars. Side 156.)

Kategori:Formelle språk