Język rekurencyjnie przeliczalny
Język rekurencyjnie przeliczalny (ang. recursively enumerable language) to język formalny określany jako język klasy 0 w hierarchii Chomsky’ego, 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
- p
- d
- e
Teoria automatów: języki formalne i gramatyki formalne
Hierarchia Chomsky’ego |
|
---|---|
Gramatyka formalna |
|
Język formalny |
|
Minimalny automat akceptujący |