Hiérarchie de Chomsky

Définition

xxxxxxx

Français

xxxxxxx

Anglais

Chomsky hierarchy

The Chomsky hierarchy is an ordering of types of grammar according to generality. The classification in fact only depends on the type of grammar rule or production used. The grammar types described in COMP9414 included:

unrestricted grammars (rules of the form a → b with no restrictions on the strings a and b)

context sensitive grammars (rules of the form a → b with the restriction length(a) <= length(b))

context free grammars (rules of the form X → b where X is a single non-terminal symbol)

regular grammars (rules of the form X → a and X → aN where X and N are non-terminal symbols, and a is a terminal symbol.)

Named after the linguist Noam Chomsky.

Source : UNWS Natural Language Processing Dictionary