Chomského normální forma

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

A → BC 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ždá bezkontextová gramatika jde snadno transformovat do Chomského normální formy.

S výjimkou volitelného pravidla S → λ (které je povoleno pro případ, kdy má gramatika generovat prázdný řetězec) jsou všechny pravidla nezkracující, tzn. při každém odvození je každý řetězec stejně dlouhý nebo delší než předcházející (ve významu času) řetězec. Jelikož všechny pravidla odvozující neterminály transformují jeden neterminál na přesně dva, parsovací strom je 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.

[editovat] Související články

• Backus-Naurova forma
• Greibachové normální forma
• Kurodova normální forma

Tento článek je příliš stručný nebo neobsahuje důležité informace.
Pomozte Wikipedii tím, že jej vhodně rozšíříte nebo alespoň nahradíte tuto šablonu nějakou konkrétnější.

---