Hierarchia Chomsky’ego
Z Wikipedii, wolnej encyclopedia
Hierarchia Chomsky’ego – stworzona przez Noama Chomsky’ego 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[1].
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[2].