Hopp til innhald

Chomsky-normalform

Frå Wikipedia – det frie oppslagsverket

Innan formelle språk er eit kontekstfritt språk sagt å vera på Chomsky-normalform om det har dei følgjande produksjonsreglane

ABC,   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 | endre wikiteksten]

Å 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 | endre wikiteksten]
  • 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.)