Linguagem recursiva

A linguagem recursiva em matemática, lógica e ciências da computação, uma linguagem formal (a definir de seqüências finitas de símbolos tomados de um fixo alfabeto ) é chamada recursiva se é um subconjunto recursivo no conjunto de todas as palavras possíveis sobre o alfabeto da linguagem. Equivalentemente, uma linguagem é recursiva se existe uma máquina de Turing que sempre pára quando recebe uma sequência finita de símbolos do alfabeto da linguagem como entrada e que aceita exatamente as palavras do alfabeto da linguagem que são parte da linguagem e rejeita todas as outras palavras. Linguagens recursivas são também chamadas de decidíveis ou Turing-decidíveis. A classe de todas as linguagens recursivas é freqüentemente chamado de R, embora este nome é usado também para a classe RP.

Este tipo de linguagem não foi definido na hierarquia de hierarquia de Chomsky de (Chomsky 1959). Todas as linguagens recursivas também são recursivamente enumeráveis.

Definições

Existem duas definições equivalentes importante 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, pára e aceita se a palavra pertence a linguagem, e pára e rejeita caso contrário. Uma máquina de Turing que sempre pára é 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 livre de contexto e linguagens sensível ao contexto são recursivas.

Propriedades de fecho

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 $L^*$
• A imagem φ(L) sob um homomorfismo livre-de-cadeia-vazia φ
• A concatenação $L \circ P$
• A união $L \cup P$
• A interseção $L \cap P$
• O complemento de L
• A subtração de conjuntos $L - P$

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

Referências

• Michael Sipser. Introduction to the Theory of Computation. [S.l.]: PWS Publishing, 1997. 151–170 p. 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.

Ver também

• Recursividade