Chomského normální forma

Chomského normální forma je vlastností formální gramatiky , pokud všechny její výstupy mají tvar:

A

\rightarrow \,BC

nebo

A

\rightarrow \,\alpha

nebo

S

\rightarrow \,\epsilon

kde , a jsou neterminální, je koncový znak (představující konstantní hodnotu), je počáteční znak a je prázdný řetězec . Také , ani nemůže být počáteční znak. $A$ $B$ $C$ $\alpha$ $S$ $\epsilon$ $B$ $C$

Každá gramatika v Chomského normální formě je bezkontextová a naopak každá bezkontextová gramatika může být efektivně převedena na ekvivalentní gramatiku v Chomského normální formě.

S výjimkou možného pravidla (používá se, když gramatika může produkovat prázdný řetězec), všechna gramatická pravidla v Chomského normální formě jsou nezkrácená; to znamená, že v procesu výstupu řetězce má každý řetězec terminálů a neterminálů vždy buď stejnou délku jako předchozí, nebo jeden další prvek. Tisk délky řetězce vždy trvá přesně kroky. Kromě toho, protože všechna neterminální pravidla odvozování překládají jeden neterminál na přesně jeden terminál nebo na přesně dva neterminály, je strom analýzy založený na gramatice normálního tvaru Chomsky binárním stromem, jehož výška je omezena délkou řetězce. $S$ $\rightarrow \,\epsilon$ $n$ $2n-1$

Díky těmto vlastnostem mnoho důkazů v teorii formálních jazyků a vyčíslitelnosti používá Chomského normální formu. Tyto vlastnosti také slouží jako základ pro různé efektivní algoritmy - například algoritmus CYK, který určuje, zda lze daný řetězec vygenerovat danou gramatikou, používá Chomského normální formu.

Pojmenováno po Noamovi Chomskym , americkém lingvistu, který navrhl Chomského hierarchii .

Alternativní definice

Některé zdroje definují Chomského normální formu poněkud odlišně.

Formální gramatika je v Chomského normální formě , pokud jsou všechny její výstupy ve tvaru:

A

\rightarrow \,BC

nebo

A

\rightarrow \,\alpha

kde , a jsou neterminálové a je koncový symbol . Při použití této definice mohou být a počáteční znaky. $A$ $B$ $C$ $\alpha$ $B$ $C$

Tato definice se od předchozí liší tím, že vylučuje možnost generování prázdného řetězce . Stále platí, že jakákoliv bezkontextová gramatika , která generuje jazyk, může být efektivně transformována do Chomského normální formy, která generuje . Hlavní výhodou poslední definice je, že důkazy jsou obecně poněkud zjednodušené, protože každý derivační krok nikdy nezkracuje délku výsledného řetězce. Jeho nevýhodou je samozřejmě to, že vyžaduje samostatné posouzení případu, kdy gramatika generuje . $\epsilon$ $L$ $L-\{\epsilon \}$ $\epsilon$

Literatura

Michael Sipser Úvod do teorie počítání . - PWS Publishing, 1997. - ISBN 0-534-94728-X . (Strany 98–101 oddílu 2.1: Bezkontextové gramatiky. Strana 156.)
John Martin . Úvod do jazyků a teorie počítání . - McGraw-Hill Education , 2003. - ISBN 0-07-232200-4 . (Strany 237–240 oddílu 6.6: zjednodušené formuláře a normální formuláře.)
John E. Hopcroft a Jeffrey D. Ullman, Úvod do teorie automatů, jazyků a počítání , Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-02988-X . (Viz kapitola 4.)
Michael A HarrisonÚvod do teorie formálních jazyků (neopr.) . - Addison-Wesley , 1978. - ISBN 978-0201029550 . (Strany 103-106.)