Chomského normální forma

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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

ABC nebo
A → α nebo
S → ε

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.[zdroj?]

S výjimkou volitelného pravidla S → ɛ (které je povoleno pro případ, kdy má gramatika generovat prázdný řetězec) 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. 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.

Související články[editovat | editovat zdroj]