thumb|Zestawy inkluzyjne opisane przez hierarchię Chomskiego Hierarchia Chomskiego – stworzona przez Noama Chomskiego hierarchia klas języków formalnych.
Hierarchia składa się z czterech klas: języki typu 3 – regularne, 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 nie wykraczają poza ograniczenia dla danej klasy.
Każdy język określonej klasy należy jednocześnie do każdej klasy poniżej, czyli: Każdy język regularny jest także bezkontekstowy. Każdy język bezkontekstowy jest także kontekstowy. Każdy język kontekstowy jest rekurencyjnie przeliczalny.
Zostało także udowodnione, że istnieje teoretyczny algorytm, który jest w stanie przekształcić daną gramatykę formalną w leżącą niżej w hierarchii.
Języki regularne (typu 3) Język regularny 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 (jeśli znajduje się on na początku lub na końcu każdego słowa – jest to odpowiednio gramatyka lewostronnie lub prawostronnie liniowa).