Linguagem recursiva

Existem duas definições equivalentes e importantes para o conceito de uma linguagem recursiva:

1. Uma linguagem formal é um subconjunto recursivo no conjunto de todas as palavras possíveis sobre o alfabeto da linguagem.
2. Uma linguagem recursiva é uma linguagem formal para a qual existe uma máquina de Turing tal que, quando é apresentada a uma entrada finita ou uma palavra, para aceitar a palavra pertence a linguagem, e para rejeitar caso contrário. Uma máquina de Turing que sempre é conhecida como um decisor e dizemos que ela decide a linguagem recursiva.

Da segunda definição, qualquer problema de decisão pode ser mostrado ser decidível exibindo-se um algoritmo para ele que termine (pare) para qualquer palavra de entrada. Um problema indecidível é um problema que não é decidível. Todas linguagens regulares, linguagens livres de contexto e linguagens sensíveis ao contexto são recursivas.

As linguagens recursivas são fechadas sobre as seguintes operações. Isto é, se L e P são duas linguagens recursivas, então as seguintes linguagens são também recursivas:

• O Fecho de Kleene ${\displaystyle L^{*}}$
• A imagem φ(L) sob um homomorfismo livre-de-cadeia-vazia φ
• A concatenação ${\displaystyle L\circ P}$
• A união ${\displaystyle L\cup P}$
• A interseção ${\displaystyle L\cap P}$
• O complemento de L
• A subtração de conjuntos ${\displaystyle L-P}$

A última propriedade decorre do fato de que a diferença do conjunto pode ser expressa em termos de interseção e complemento.

• Recursividade

• Michael Sipser (1997). «Decidability». Introduction to the Theory of Computation. [S.l.]: PWS Publishing. pp. 151–170. ISBN 0-534-94728-X 
• Chomsky, Noam (1959). «On certain formal properties of grammars». Information and Control. 2 (2): 137–167. doi:10.1016/S0019-9958(59)90362-6