Question

PERGUNTA 3
Leia o excerto a seguir:
“Uma máquina de Turing é um autômato cuja fita não possui tamanho máximo e pode ser usada, simultaneamente, como dispositivo de entrada, como dispositivo de saída e como memória de trabalho. Partindo desse pressuposto, temos que as linguagens recursivamente enumeráveis ou linguagens tipo 0, por sua vez, são fundamentais na aplicabilidade da máquina de Turing.

MENEZES, P. B. Linguagens formais e autômatos . São Paulo: Sagah, 2015. p. 167.

A respeito da teoria das linguagens recursivas e de sua aplicabilidade quanto a máquina de Turing, analise as afirmativas a seguir e assinale V para a(s) Verdadeira(s) e F para a(s) Falsa(s).

I. ( ) Podemos considerar que, segundo a hipótese de Church, a máquina de Turing é o dispositivo computacional mais geral.
II. ( ) Algumas classes de linguagens podem representar as linguagens recursivamente enumeráveis usando um formalismo axiomático.
III. ( ) Uma gramática irrestrita possuirá qualquer restrição quanto à forma das produções, conforme o modelo de Turing.
IV. ( ) O formalismo gramatical não possui o mesmo poder computacional que o formalismo da máquina de Turing.

Assinale a alternativa que apresenta a sequência correta.

a) F, V, F, F.

b) V, V, F, F.

c) V, V, F, V.

d) F, V, F, V.

e) V, F, V, V.

Answer 1

Resposta:

b) V, V, F, F.

Explicação:

De fato, a hipótese de Church, ao tratar da máquina de Turing, tem ela omo o dispositivo computacional mais geral e algumas classes de linguagens podem receber a designação de recursivamente enumeráveis, tratando-se, então de um formalismo axiomático.