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 
Å 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 

 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.)
Kategori:Formelle språk