INF05005/11-LRE

A Classe da Linguagens Recursivamente Enumeráveis é aquela que contém:

• Linguagens reconhecidas por um Autômato com Pilha

• Somente linguagens Turing-decidíveis

• Linguagens menos expressivas do que as da Classe das LLC

• Todas as linguagens Turing-reconhecíveis

Dada uma LRE L qualquer, uma Máquina de Turing M tal que ACEITA(M) = L e uma palavra w, é CORRETO afirmar que:

• M sempre para caso w ∉ ACEITA(M)

• w pode pertencer à LOOP(M)

• M nunca para caso w ∉ ACEITA(M)

• Se w ∈ REJEITA(M), então existe uma MT que sempre para para w

Uma linguagem é recursiva quando uma MT que a reconhece:

• Sempre para

• Pode não parar

• Nunca para

• Não existe

Uma linguagem é NÃO recursivamente enumerável quando:

• Existe só uma MT que a reconhece

• Existe uma MT que a decide

• Não existe qualquer MT que a reconheça

• Uma MT sempre rejeita as suas palavras

Em termos de cardinalidades, o conjunto das LRE e o conjunto das LNRE são, respectivamente:

• Enumerável e Contável

• Contável e Enumerável

• Enumerável e Não Contável

• Não Enumerável e Não Contável

Uma das propriedades de LRE é que:

• Seu complemento é sempre uma LRE

• Contém propriamente todas as linguagens recursivas

• Sempre é recursiva

• Não pode ser reconhecida por um Autômato com Duas Pilhas

Se uma linguagem L é LRE, então:

• Seu complemento é sempre LNRE

• Ela pode ser Turing-decidível

• Sempre pode ser descrita por uma Gramática Livre de Contexto

• É reconhecida por um Autômato com Um Pilha

Dadas uma linguagem L e sua linguagem complemento ~L, uma combinação IMPOSSÍVEL é:

• L é recursiva e ~L é recursiva

• L é LRE e ~L é recursiva

• L é recursiva e ~L não é LRE

• L é RE e ~L não é LRE