Que isso hei!! Hierarquia de chomsky.
Basicamente é isso pessoal:
1) Linguagens finitas.
2) Linguagens regulares.
3) Linguagens livres de contexto .
4) Linguagens sensíveis ao contexto.
5)Linguagens recursivas(decidíveis).
6) Linguagens recursivamente enumeráveis (semi-decidíveis).
7) Linguagens irrestritas;
Cada nível engloba o seu nível inferior, ou seja, o nível 7 engloba todas as outra linguagens e assim em diante....
GABARITO ALTERNATIVA E
E) a classe das linguagens recursivas é um subconjunto estrito da classe das linguagens recursivamente enumeráveis.
CORRETO, pois o nível 5 (linguagens recursivas) é um subconjunto do nível 6 (linguagens recursivamente enumeráveis);
Uma imagem vale mais que mil palavras, então: www.encurtador.com.br/mAFMV
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, 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.
Existem três equivalentes definições importantes para o conceito de uma linguagem recursivamente enumerável:
1)Uma linguagem recursivamente enumerável formal é um subconjunto recursivamente enumerável no conjunto de todas as palavras possíveis sob o alfabeto da linguagem.
2)Uma linguagem recursivamente enumerável é uma linguagem formal para a qual existe uma máquina de Turing que irá enumerar todas as cadeias válidas da linguagem. Note que, se a linguagem é infinita, o algoritmo de enumeração fornecido pode ser escolhido de forma que evite repetições, uma vez que podemos testar se a cadeia produzida para o número n é já é produzida para um número que é inferior a n. Se ela já é produzida, use a saída da entrada n+1 (recursivamente), mas mais uma vez, teste se é uma cadeia nova.
3)(Resposta da Questão) Uma linguagem recursivamente enumerável é uma linguagem formal para a qual existe uma máquina de Turing que irá parar e aceitar quando se roda com qualquer cadeia da linguagem na entrada e pode parar e rejeitar ou entrar em loop quando se roda com qualquer cadeia que não é da linguagem. Esta é a diferença entre linguagem recursiva, que exige que a máquina de Turing sempre pare.