Hierarchia Chomsky'ego

Z Wikipedii

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 - 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 przestrzegają ograniczeń dla danej klasy.

Spis treści 1 Języki regularne (typu 3) 2 Języki bezkontekstowe (typu 2) 3 Języki kontekstowe (typu 1) 4 Języki rekurencyjnie przeliczalne (typu 0) 5 Zależności między klasami 6 Znaczenie

[edytuj] 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 (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:

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

[edytuj] 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.:

dowolne reguły gramatyk regularnych

• jeśli dla danego języka istnieje gramatyka bezkontekstowa, istnieje też równoważna gramatyka bezkontekstowa w postaci normalnej Chomsky'ego i postaci normalnej Greibach.
• Gramatyki bezkontekstowe są równoważne niedeterministycznym automatom ze stosem.

[edytuj] Języki kontekstowe (typu 1)

Język kontekstowy to język, który można wygenerować za pomocą gramatyki kontekstowej, której produkcje są postaci , gdzie α i β są dowolnymi słowami, A nieterminalem, γ - niepustym słowem.

Dodatkowo pozwala się na regułę postaci , 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 są dozwolone tylko w tych pierwszych.

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

[edytuj] Języki rekurencyjnie przeliczalne (typu 0)

Język rekurencyjnie przeliczalny to język, dla którego istnieje gramatyka typu 0, której produkcje są postaci , gdzie α i β są dowolnymi słowami.

• Gramatyki typu 0 są równoważne maszynom Turinga.

[edytuj] 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, klasy języków kolejnych typów zawierają się w sobie. Zawierania te są ostre, tzn. istnieją języki bezkontekstowe, które nie są regularne, kontekstowe, które nie są bezkontekstowe, oraz rekurencyjnie przeliczalne, które nie są kontekstowe.

[edytuj] 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 rekurencyjnie przeliczalnych ma dokładnie taką moc jak maszyny Turinga, języki bezkontekstowe odpowiadają niedeterministycznym automatom ze stosem, regularne zaś automatom skończonym.

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