Chomsky normal form

Chomsky normalform är en egenskap hos en formell grammatik om alla dess utdata är av formen:

A

\rightarrow \,BC

eller

A

\rightarrow \,\alpha

eller

S

\rightarrow \,\epsilon

där , och är icke-terminaler, är ett terminaltecken (representerar ett konstant värde), är ett starttecken och är den tomma strängen . Dessutom kan varken , eller vara en startkaraktär. $A$ $B$ $C$ $\alfa$ $S$ $\epsilon$ $B$ $C$

Varje grammatik i Chomsky normalform är kontextfri , och omvänt kan varje sammanhangsfri grammatik effektivt konverteras till en motsvarande grammatik i Chomsky normalform.

Med undantag för en möjlig regel (används när grammatiken kan producera den tomma strängen), är alla grammatikregler i Chomsky normalform icke-förkortande; det vill säga, i processen att mata ut en sträng, har varje kedja av terminaler och icke-terminaler alltid antingen samma längd som den föregående, eller ytterligare ett element. Att skriva ut en längdsträng tar alltid exakta steg. Dessutom, eftersom alla icke-terminala slutledningsregler översätter en icke-terminal till exakt en terminal eller till exakt två icke-terminaler, är analysträdet baserat på Chomskys normalforms grammatik ett binärt träd vars höjd begränsas av längden på strängen. $S$ $\rightarrow \,\epsilon$ $n$ $2n-1$

På grund av dessa egenskaper använder många bevis i teorin om formella språk och beräkningsbarhet Chomskys normala form. Dessa egenskaper fungerar också som grund för olika effektiva algoritmer - till exempel använder CYK-algoritmen som avgör om en given sträng kan genereras av en given grammatik Chomsky normalform.

Uppkallad efter Noam Chomsky , den amerikanske lingvisten som föreslog Chomsky-hierarkin .

Alternativ definition

Vissa källor definierar Chomskys normala form något annorlunda.

En formell grammatik är i Chomsky normal form om alla dess utdata är av formen:

A

\rightarrow \,BC

eller

A

\rightarrow \,\alpha

där , och är icke-terminaler, och är terminalsymbolen för . När du använder denna definition , och kan vara initiala tecken. $A$ $B$ $C$ $\alfa$ $B$ $C$

Denna definition skiljer sig från den tidigare genom att den utesluter möjligheten att generera en tom sträng . Det är fortfarande sant att all kontextfri grammatik som genererar ett språk effektivt kan omvandlas till en Chomsky-normalform som genererar . Den huvudsakliga fördelen med den sista definitionen är att bevisen i allmänhet är något förenklade, eftersom varje härledningssteg aldrig minskar längden på den resulterande strängen. Naturligtvis är dess nackdel att det kräver en separat övervägande av fallet när grammatiken genererar . $\epsilon$ $L$ $L-\{\epsilon \}$ $\epsilon$

Litteratur

Michael Sipser Introduktion till teorin om beräkning . - PWS Publishing, 1997. - ISBN 0-534-94728-X . (Sidorna 98-101 i avsnitt 2.1: sammanhangsfria grammatiker. Sida 156.)
John Martin . Introduktion till språk och beräkningsteori . - McGraw-Hill Education , 2003. - ISBN 0-07-232200-4 . (Sidorna 237-240 i avsnitt 6.6: förenklade former och normala former.)
John E. Hopcroft och Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation , Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-02988-X . (Se kapitel 4.)
Michael A HarrisonIntroduktion till formell språkteori (neopr.) . - Addison-Wesley , 1978. - ISBN 978-0201029550 . (Sid 103-106.)