Chomského normální forma

Kategorie: Nezařazeno (celkem: 23179 referátů a seminárek)

Informace o referátu:

Příbuzná témata



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.

Související články




Nový příspěvek


Ochrana proti spamu. Kolik je 2x4?



Na-mobil.cz

Spřátelené weby

Přidat stránku k oblíbeným

Nejnovější v diskusi

Diskusní fórum »

TIP: Chcete zkrátit dlouho chvíli sobě nebo blízkému?
Klikněte na Puzzle-prodej.cz a vyberte si z 5000 motivů skladem!
TIP: Hračky a hry za dobré ceny?
Klikněte na Hračky obchod.cz a vyberte si z tisícovky hraček skladem!