Saltar para o conteúdo

Linguagem recursiva

Origem: Wikipédia, a enciclopédia livre.

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.

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

[editar | editar código-fonte]

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

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

[editar | editar código-fonte]
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