Hopp til innhold

Chomsky normalform

Fra Wikipedia, den frie encyklopedi

I formelle språk er et kontekstfritt språk sagt å være på chomsky normalform om det har følgende produksjonsregler

ABC,   eller
Aa,   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]