Hierarchia Chomsky'ego to stworzona przez Noama Chomsky'ego hierarchia klas języków formalnych.

Hierarchia składa się z czterech klas:

• języki typu 3 - liniowe
• języki typu 2 - bezkontekstowe
• języki typu 1 - kontekstowe
• języki typu 0 - rekurencyjnie przeliczalne

Język należy do danej klasy wtedy i tylko wtedy, gdy jest możliwe zbudowanie gramatyki formalnej, która generuje dany język, a której reguły przestrzegają ograniczeń dla danej klasy.

Języki liniowe (typu 3)

Język liniowy to język, który można wygenerować za pomocą gramatyki liniowej – takiej, która po lewej stronie reguł ma pojedyncze nieterminale, po prawej zaś słowa zawierające co najwyżej jeden nieterminal (na początku lub na końcu każdego słowa - jest to wtedy odpowiednio gramatyka lewostronnie lub prawostronnie liniowa). Poprawne reguły to na przykład:

$A\backslash rightarrow\; \backslash epsilon$

$A\backslash rightarrow\; a$

$A\backslash rightarrow\; abc$

$A\backslash rightarrow\; B$

$A\backslash rightarrow\; aB$

$A\backslash rightarrow\; abcB$

Języki bezkontekstowe (typu 2)

Język bezkontekstowy to język, który można wygenerować za pomocą gramatyki bezkontekstowej, która po lewej stronie reguł ma pojedyncze nieterminale, po prawej zaś dowolne słowa. Np.:

$A\backslash rightarrow\; aBc$

$A\backslash rightarrow\; BC$

dowolne reguły gramatyk regularnych

Języki kontekstowe (typu 1)

Język kontekstowy to język, który można wygenerować za pomocą gramatyki kontekstowej, która po lewej stronie reguł ma słowo nie dłuższe niż po prawej, np.:

$AB\backslash rightarrow\; CD$

$AB\backslash rightarrow\; CdE$

$ABcd\backslash rightarrow\; abCD$

Dodatkowo pozwala się na regułę postaci $S\backslash rightarrow\; \backslash epsilon$, tzn. z symbolu startowego w słowo puste, ale tylko w przypadku jeżeli słowo startowe nie występuje po prawej stronie żadnej reguły.

Nie każda reguła języków bezkontekstowych jest poprawną regułą języków kontekstowych. Reguły postaci $A\backslash rightarrow\; \backslash epsilon$ są dozwolone tylko w tych pierwszych.

Mimo to jednak wszystkie języki bezkontekstowe są językami kontekstowymi:

• jeśli dla danego języka istnieje gramatyka bezkontekstowa, istnieje też gramatyka bezkontekstowa w postaci normalnej Chomsky'ego
• wszystkie reguły postaci normalnej Chomsky'ego są też poprawnymi regułami gramatyk kontekstowych

Języki rekursywnie przeliczalne (typu 0)

Język rekursywnie przeliczalny to język, dla którego istnieje gramatyka formalna dowolnej postaci.

Zależności między klasami

Ponieważ (z poprawką na zależność między gramatykami bezkontekstowymi a kontekstowymi) gramatyka typu o mniejszym numerze dopuszcza wszystkie reguły gramatyk o numerze większym, i jeszcze jakieś inne, widać od razu, że klasy języków kolejnych typów zawierają się w sobie. Można udowodnić też, że istnieją języki bezkontekstowe, które nie są liniowe, kontekstowe, które nie są bezkontekstowe, oraz rekursywnie przeliczalne, które nie są kontekstowe.

Znaczenie

Hierarchia Chomsky'ego wydziela 4 klasy języków, ale możliwe jest przecież stworzenie wielu innych klas, przez odmienne ograniczenia na postać reguł czy inne właściwości języka. Trzy z 4 klas są dość ważne – klasa języków rekursywnie przeliczalnych ma dokładnie taką moc jak maszyny Turinga, języki bezkontekstowe odpowiadają niedeterministycznym automatom ze stosem, liniowe zaś automatom skończonym.

Spośród czterech klas hierarchii, najmniejsze znaczenie zarówno teoretyczne jak i praktyczne ma klasa języków kontekstowych.

Języki formalne

Chomsky-hiërargie | Йерархия на Чомски | Chomského hierarchie | Chomsky-Hierarchie | Chomsky–Schützenberger hierarchy | Jerarquía de Chomsky | Hiérarchie de Chomsky | 촘스키 위계 | Gerarchia di Chomsky | チョムスキー階層 | Hierarquia de Chomsky | Ierarhia Chomsky | Chomského hierarchia | Chomskyn hierarkia | 乔姆斯基谱系