Přeskočit na obsah

Chomského normální forma

Z Wikipedie, otevřené encyklopedie

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

ABC 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.[1]

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. 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.

  1. MELICHAR, Bořivoj. Jazyky a překlady. Praha: České vysoké učení technické v Praze, 2007. 256 s. ISBN 978-80-01-02776-9. Kapitola 3.4.1, s. 120. 

Související články

[editovat | editovat zdroj]