Wersja z 17:10, 26 mar 2010 edytuj VolkovBot (dyskusja \| edycje) 273 422 edycje m robot dodaje: uk:Ієрархія Чомскі ← poprzednia edycja		Wersja z 03:24, 1 lip 2010 edytuj anuluj edycję Xqbot (dyskusja \| edycje) Boty 327 495 edycji m robot poprawia: fa:وراثت چامسکی; zmiany kosmetyczne następna edycja →
Linia 9: Język należy do danej klasy wtedy i tylko wtedy, gdy jest możliwe zbudowanie [[gramatyka formalna\|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) == '''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: :<math>A\rightarrow \epsilon</math> :<math>A\rightarrow a</math> Linia 19: :<math>A\rightarrow abcB</math> * Gramatyki liniowe są równoważne [[deterministyczny automat skończony\|automatom skończonym]]. == 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.: Linia 30: * jeśli dla danego języka istnieje gramatyka bezkontekstowa, istnieje też równoważna gramatyka bezkontekstowa w [[postać normalna Chomsky'ego\|postaci normalnej Chomsky'ego]] i [[postać normalna Greibach\|postaci normalnej Greibach]]. * Gramatyki bezkontekstowe są równoważne [[Automat ze stosem\|niedeterministycznym automatom ze stosem]]. == 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 <math>\alpha A \beta \rightarrow \alpha \gamma \beta</math>, gdzie α i β są dowolnymi słowami, A nieterminalem, γ - niepustym słowem. Linia 45: Reguły postaci <math>A\rightarrow \epsilon</math> są dozwolone tylko w tych pierwszych. * Gramatyki kontekstowe są równoważne [[automat liniowo ograniczony\|automatom liniowo ograniczonym]]. == 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 <math>\alpha \rightarrow \beta </math>, gdzie α i β są dowolnymi słowami. * Gramatyki typu 0 są równoważne [[maszyna Turinga\|maszynom Turinga]]. == 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. == 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 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]]. [[Kategoria:Języki formalne]] Linia 73: [[en:Chomsky hierarchy]] [[es:Jerarquía de Chomsky]] [[fa:وراثت ~~چامسکى~~چامسکی]] [[fr:Hiérarchie de Chomsky]] [[ko:촘스키 위계]]

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