Chomského normální forma

Chomského normální forma je tvar formální gramatiky ve které jsou všechna odvozovací pravidla tvaru:

:A → BC nebo :A → α nebo :S → ε (je povoleno pokud gramatika generuje prázdný řetězec a zároveň se S nevyskytuje na pravé straně žádného pravidla)

kde A, B a C jsou neterminály, α je terminál, S je startovní neterminál a ε je prázdný řetězec, přičemž B ani C nemohou být startovacím neterminálem.

Každá gramatika v Chomského normální formě je bezkontextová a naopak, každou bezkontextovou gramatiku lze transformovat do Chomského normální formy.

S výjimkou volitelného pravidla S → ɛ jsou všechna pravidla nezkracující, tzn. při každém odvození je každý řetězec stejně dlouhý nebo delší než předchozí (ve významu času) řetězec. +more Jelikož všechna pravidla odvozující neterminály transformují jeden neterminál na právě dva, je parsovacím stromem binární strom a jeho výška je maximálně délka generovaného řetězce.

Forma je pojmenována po svém autorovi, Noamovi Chomském.

Chomského normální forma je často používána v CYK algoritmu.

Odkazy

Reference

Související články

Backusova-Naurova forma * Greibachové normální forma * Kurodova normální forma

Kategorie:Formální jazyky