Llenguatge enumerable recursivament
En matemàtiques, lògica i complexitat computacional un llenguatge formal és un llenguatge enumerable recursivament (o també parcialment decidible o Turing-computable) si és un subconjunt enumerable recursivament del conjunt de totes les paraules amb l'alfabet del llenguatge. Equivalentment, un llenguatge és enumerable recursivament si existeix una màquina de Turing que accepta i s'atura amb qualsevol cadena del llenguatge.[1][2][3]
Aquest tipus de llenguatges s'etiqueten com de tipus 0 en la jerarquia de Chomsky dels llenguatges formals. Tots els llenguatges regulars, lliures de context i recursius son llenguatges enumerables recursivament.
La classe de tots els llenguatges enumerables recursivament s'anomena RE.
Definicions
[modifica]Hi ha tres definicions equivalents d'un llenguatge enumerable recursivament:
- Un llenguatge enumerable recursivament és un subconjunt enumerable recursivament del conjunt de totes les possibles paraules de l'alfabet del llenguatge.
- Un llenguatge enumerable recursivament és un llenguatge formal pel que existeix una màquina de Turing (o alguna altra funció computable) que enumerarà totes les cadenes vàlides del llenguatge.
- Un llenguatge enumerable recursivament és un llenguatge formal pel que existeix una màquina de Turing (o alguna altra funció computable) que s'aturarà i acceptarà quan se li presenti qualsevol cadena del llenguatge com a entrada, però que o bé s'aturarà i rebutjarà o no s'aturarà mai quan la cadena no sigui del llenguatge. Això diferència aquest tipus de llenguatge dels llenguatges recursius, on la màquina ha d'aturar-se en tots els casos.
Tots els llenguatges regulars, lliures de context i recursius son llenguatges enumerables recursivament.
El teorema de Post demostra que la classe RE juntament amb la seva complementaria co-RE es corresponent al primer nivell de la jerarquia aritmètica.
Propietats de clausura
[modifica]Els llenguatges enumerables recursivament són tancats segons les següents operacions. Si L i P són dos llenguatges enumerables recursivament, llavors els següents llenguatges també ho són:
- la clausura de Kleene
- la concatenació
- la unió
- la intersecció
Els llenguatges enumerables recursivament no estan tancats respecte a la diferència de conjunts o complementari. El conjunt diferència L - P pot ser o pot no ser enumerable recursivament. Si L és enumerable recursivament, llavors el complement d'L és enumerable recursivament si i només si L és també recursiu.
Vegeu també
[modifica]Referències
[modifica]- ↑ «Complexity Zoo:R - Complexity Zoo» (en anglès). Arxivat de l'original el 2017-07-21. [Consulta: 28 novembre 2018].
- ↑ Michael., Sipser,. Introduction to the theory of computation. 2a edició. Boston: Thomson Course Technology, 2006. ISBN 0534950973.
- ↑ 1951-, Kozen, Dexter,. Automata and computability. Nova York: Springer, 1997. ISBN 0387949070.
| ||||||||||
Cada categoria de llenguatges, excepte aquells marcats per *, és un subconjunt de la categoria superior. Qualsevol llenguatge en aquesta categoria es genera per una gramàtica i per un autòmat de la categoria de la mateixa línia. |
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.