Język rekurencyjnie przeliczalny

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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[edytuj | edytuj kod]

Istnieje kilka równoważnych definicji języka rekurencyjnie przeliczalnego:

  1. Rekurencyjnie przeliczalny podzbiór zbioru wszystkich słów nad danym alfabetem.
  2. Język formalny, dla którego istnieje maszyna Turinga lub inna funkcja obliczalna, która jest w stanie ponumerować wszystkie słowa języka.
  3. Język formalny L, dla którego problem czy słowo x \in L jest nierozstrzygalny[1].

Własności[edytuj | edytuj kod]

Języki rekurencyjnie przeliczalne są zamknięte ze względu na następujące operacje:

Zobacz też[edytuj | edytuj kod]

Przypisy