Hierarchia Chomsky’ego


Hierarchia Chomsky’ego w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania Zestawy inkluzyjne opisane przez hierarchię Chomsky’ego

Hierarchia Chomsky’ego – stworzona przez Noama Chomsky’ego hierarchia klas języków formalnych.

Hierarchia składa się z czterech klas:

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.

Spis treści

Języki regularne (typu 3) | edytuj kod

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). Poprawne reguły to na przykład:

A ϵ , {\displaystyle A\to \epsilon ,} A a , {\displaystyle A\to a,} A a b c , {\displaystyle A\to abc,} A B , {\displaystyle A\to B,} A a B , {\displaystyle A\to aB,} A a b c B . {\displaystyle A\to abcB.}

Języki bezkontekstowe (typu 2) | edytuj kod

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 a B c , {\displaystyle A\to aBc,} A B C , {\displaystyle A\to BC,} a także dowolne reguły gramatyk regularnych.

Języki kontekstowe (typu 1) | edytuj kod

Język kontekstowy to język, który można wygenerować za pomocą gramatyki kontekstowej, której produkcje są postaci α A β α γ β , {\displaystyle \alpha A\beta \to \alpha \gamma \beta ,} gdzie α {\displaystyle \alpha } i β {\displaystyle \beta } są dowolnymi słowami, A jest symbolem nieterminalnym, γ {\displaystyle \gamma } – niepustym słowem.

A B C D B {\displaystyle AB\to CDB} A B C d E B {\displaystyle AB\to CdEB} A B c d a b C D B c d {\displaystyle ABcd\to abCDBcd} B b {\displaystyle B\to b}

Dodatkowo pozwala się na regułę postaci S ϵ , {\displaystyle S\to \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 ϵ {\displaystyle A\to \epsilon } są dozwolone tylko w tych pierwszych.

Języki rekurencyjnie przeliczalne (typu 0) | edytuj kod

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

Zależności między klasami | edytuj kod

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.

Znaczenie | edytuj kod

Hierarchia Chomsky’ego wydziela 4 klasy języków, ale możliwe jest stworzenie wielu innych klas, przez odmienne ograniczenia na postać reguł czy inne właściwości języka. Trzy z czterech 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.

Kontrola autorytatywna:
Na podstawie artykułu: "Hierarchia Chomsky’ego" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy