Chomsky-normalform
Innan formelle språk er eit kontekstfritt språk sagt å vera på Chomsky-normalform om det har dei følgjande produksjonsreglane
- A → BC, eller
- A → a, eller
- S → ε
Her er A, B og C ikkje-terminalsymbol og a er eit terminalsymbol. S er startsymbolet og ε er den tomme strengen. Korkje B eller C kan vera startsymbolet og den tredje produksjonregelen kan berre vera med om den tomme strengen er i det gjevne kontekstfrie språket.
Kvart og eit kontekstfritt språk kan ved å følgja eit sett med reglar verta til gjort om til Chomsky-normalform og kvart og eit språk gjeve på Chomsky-normalform er eit kontekstfritt språk.
Bruksområde
endreÅ få eit språk på Chomsky-normalform er ofte brukt som eit preprosesseringssteg i fleire algoritmar. Kontekstfrie språk er viktige innanfor mellom anna kompilatorteknikk. Det vert enklare å jobba med kontekstfrie språk når alle kontekstfrie språk kan omformast til denne forma.
Litteratur
endre- 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.)