Hierarchia Chomsky'ego

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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.

Języki regularne (typu 3)[edytuj | 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\rightarrow \epsilon
A\rightarrow a
A\rightarrow abc
A\rightarrow B
A\rightarrow aB
A\rightarrow abcB

Języki bezkontekstowe (typu 2)[edytuj | 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\rightarrow aBc
A\rightarrow BC
A także dowolne reguły gramatyk regularnych.

Języki kontekstowe (typu 1)[edytuj | edytuj kod]

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

AB\rightarrow CDB
AB\rightarrow CdEB
ABcd\rightarrow abCDBcd
B\rightarrow b

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

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

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

Zależności między klasami[edytuj | 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 | 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.