Hierarchia Chomsky’ego: Różnice pomiędzy wersjami
[wersja przejrzana] | [wersja przejrzana] |
Usunięta treść Dodana treść
m →Znaczenie: ujednolicenie zapisu |
m →Znaczenie: źródła... |
||
Linia 61:
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]].
Spośród czterech klas hierarchii, najmniejsze znaczenie zarówno teoretyczne jak i praktyczne ma klasa języków kontekstowych{{fakt}}.
[[Kategoria:Języki formalne]]
|