Linguagem recursiva

A linguagem recursiva em matemática, lógica e ciência da computação, uma linguagem formal (a definir de sequê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 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.

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 ∗ {\displaystyle L^{*}}
  • A imagem φ(L) sob um homomorfismo livre-de-cadeia-vazia φ
  • A concatenação L ∘ P {\displaystyle L\circ P}
  • A união L ∪ P {\displaystyle L\cup P}
  • A interseção L ∩ P {\displaystyle L\cap P}
  • O complemento de L
  • A subtração de conjuntos L − P {\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.

Teoria da computação

Teoria de autômatos: linguagem formal e gramática formal
Hierarquia
Chomsky 		Gramática Linguagem Reconhecedor
Tipo-0 Irrestrita Recursivamente enumerável Máquina de Turing
-- -- Recursiva Máquina de Turing que sempre para
Tipo-1 Sensível ao contexto Sensível ao contexto Autômato linearmente limitado
Tipo-2 Livre de contexto Livre de contexto Autômato com pilha
Tipo-3 Regular Regular Autômato finito


Ver também

Referências

  • 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