Llenguatge recursiu

En matemàtiques, lògica i complexitat computacional un llenguatge formal és un llenguatge recursiu és un subconjunt recursiu del conjunt de totes les seqüències finites possibles de l'alfabet del llenguatge. Un llenguatge es recursiu si existeix una màquina de Turing que sempre s'atura quan rep una paraula del llenguatge com entrada, ja sigui per acceptar-la o per rebutjar-la. També s'anomenen llenguatges decidibles.[1][2]

La classe de tots els llenguatges recursius s'anomena R.

Aquest tipus de llenguatge no està definit a la jerarquia de Chomsky. Tots els llenguatges recursius son també enumerables recursivament. Tots els llenguatges regulars, lliures de context i sensibles al context son llenguatges recursius.

Definició modifica

Hi ha dues definicions equivalents pel concepte de llenguatge recursiu:

  1. Un llenguatge recursiu és un subconjunt recursiu del conjunt de totes les possibles paraules de l'alfabet d'un llenguatge.
  2. Un llenguatge recursiu és un llenguatge formal pel qual existeix una màquina de Turing que, quan rep qualsevol entrada finita, sempre s'atura i accepta o rebutja l'entrada segons si la paraula es del llenguatge.

Per la definició 2, qualsevol problema de decisió es pot demostrar si és decidible dissenyant un algorisme que sempre s'atura per qualsevol entrada.

Propietats de Clausura modifica

Els llenguatges recursius son tancats segons les següents operacions. Sigui L i P dos llenguatges recursius, llavors el resultat d'aquestes operacions també ho son:

  • Clausura de Kleene  
  • La imatge φ(L) amb un homomorfisme
  • La concatenació  
  • La unió  
  • La intersecció  
  • El complement de L
  • El conjunt diferència L-P

Vegeu també modifica

Referències modifica

  1. Michael., Sipser,. Introduction to the theory of computation. 3a edició. Boston, MA: Cengage Learning, 2013. ISBN 9781133187790. 
  2. Immerman, Neil. Computability and Complexity. Spring 2016. Metaphysics Research Lab, Stanford University, 2016.