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 gdzie i są dowolnymi słowami.
Gramatyki typu 0 są równoważne 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 Chomskiego 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.
Przypisy
Bibliografia
Kategoria:Języki formalne