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 | rediger kilde]Å 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 | rediger kilde]- 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.)