Hierarchia Chomsky’ego

Hierarchia Chomsky’ego

Hierarchia Chomsky’ego, opracowana przez Noama Chomsky’ego, klasyfikuje języki formalne w cztery kategorie:

• 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, jeśli można zbudować gramatykę formalną spełniającą określone reguły dla tej klasy. Języki klasy wyższej obejmują języki klas niższych, co oznacza, że:

• Każdy język regularny jest bezkontekstowy.
• Każdy język bezkontekstowy jest kontekstowy.
• Każdy język kontekstowy jest rekurencyjnie przeliczalny.

Udowodniono również, że istnieje algorytm przekształcający gramatykę formalną w gramatykę klasy niższej.

Języki regularne (typu 3)

Język regularny można wygenerować za pomocą gramatyki liniowej, gdzie reguły mają pojedyncze nieterminale po lewej stronie i słowa z maksymalnie jednym nieterminalem po prawej. Przykłady reguł to:

• $A\; \backslash to\; \backslash epsilon$
• $A\; \backslash to\; a$
• $A\; \backslash to\; abc$

Gramatyki liniowe są równoważne automatom skończonym.

Języki bezkontekstowe (typu 2)

Język bezkontekstowy można wygenerować za pomocą gramatyki bezkontekstowej, gdzie reguły mogą mieć dowolne słowa po prawej stronie:

• $A\; \backslash to\; aBc$
• $A\; \backslash to\; BC$

Gramatyki bezkontekstowe są równoważne niedeterministycznym automatom ze stosem.

Języki kontekstowe (typu 1)

Język kontekstowy można wygenerować z gramatyki kontekstowej, która ma produkcje postaci $\backslash alpha\; A\; \backslash beta\; \backslash to\; \backslash alpha\; \backslash gamma\; \backslash beta$. Przykłady:

• $AB\; \backslash to\; CDB$
• $AB\; \backslash to\; CdEB$

Gramatyki kontekstowe są równoważne automatom liniowo ograniczonym.

Języki rekurencyjnie przeliczalne (typu 0)

Język rekurencyjnie przeliczalny generowany jest przez gramatykę typu 0, z produkcjami w postaci $\backslash alpha\; \backslash to\; \backslash beta$. Gramatyki te są równoważne maszynom Turinga.

Zależności między klasami

Gramatyki typu o mniejszym numerze dopuszczają reguły gramatyk o numerze większym, co prowadzi do ostrych zawierań klas. Istnieją języki, które są bezkontekstowe, ale nie regularne, kontekstowe, które nie są bezkontekstowe, oraz rekurencyjnie przeliczalne, które nie są kontekstowe.

Znaczenie

Hierarchia Chomsky’ego definiuje cztery podstawowe klasy języków formalnych, z których trzy są szczególnie istotne w teorii automatyki i języków formalnych. Języki rekurencyjnie przeliczalne mają moc równą maszynom Turinga, a języki bezkontekstowe odpowiadają niedeterministycznym automatom ze stosem.