Hierarchia Chomsky’ego: Różnice pomiędzy wersjami

'''Hierarchia Chomsky'egoChomsky’ego''' – stworzona przez [[Noam Chomsky|Noama Chomsky'egoChomsky’ego]] hierarchia klas [[język formalny|języków formalnych]].

* [[język regularny|języki typu 3 -– regularne]]

* [[język bezkontekstowy|języki typu 2 -– bezkontekstowe]]

* [[język kontekstowy|języki typu 1 -– kontekstowe]]

* [[językJęzyk rekursywnierekurencyjnie przeliczalny|języki typu 0 -– rekurencyjnie przeliczalne]]

'''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:

: <math>A\rightarrow \epsilon</math>

: <math>A\rightarrow a</math>

: <math>A\rightarrow abc</math>

: <math>A\rightarrow B</math>

: <math>A\rightarrow aB</math>

: <math>A\rightarrow abcB</math>

: <math>A\rightarrow aBc</math>

: <math>A\rightarrow BC</math>

: A także dowolne reguły gramatyk regularnych.

* jeśli dla danego języka istnieje gramatyka bezkontekstowa, istnieje też równoważna gramatyka bezkontekstowa w [[postać normalna Chomsky'ego|postaci normalnej Chomsky'egoChomsky’ego]] i [[postać normalna Greibach|postaci normalnej Greibach]].

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

: <math>AB\rightarrow CDB</math>

: <math>AB\rightarrow CdEB</math>

: <math>ABcd\rightarrow abCDBcd</math>

: <math>B\rightarrow b</math>

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

* Gramatyki typu 0 są równoważne [[maszyna Turinga|maszynom Turinga]].

Hierarchia Chomsky'egoChomsky’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 [[maszyna Turinga|maszyny Turinga]], języki bezkontekstowe odpowiadają [[Automat ze stosem|niedeterministycznym automatom ze stosem]], regularne zaś [[deterministyczny automat skończony|automatom skończonym]].