Język rekurencyjnie przeliczalny (ang. recursively enumerable language) – język formalny określany jako język klasy 0 w hierarchii Chomskiego, który generowany jest przez gramatykę kombinatoryczną.
Definicje Istnieje kilka równoważnych definicji języka rekurencyjnie przeliczalnego:
Rekurencyjnie przeliczalny podzbiór zbioru wszystkich słów nad danym alfabetem. Język formalny, dla którego istnieje maszyna Turinga lub inna funkcja obliczalna, która jest w stanie ponumerować wszystkie słowa języka.
Własności Języki rekurencyjnie przeliczalne są zamknięte ze względu na następujące operacje:
Domknięcie Kleene'ego z L Konkatenację języków L oraz P Sumę Przecięcie
Zobacz też funkcja rekurencyjna teoria rekursji
Kategoria:Języki formalne