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
redigerÅ 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
rediger- Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. (side 98–101 seksjon 2.1: context-free grammars. Side 156.)