Acerca das características dos problemas decidíveis e indecidíveis e das diferentes linguagens da hierarquia de Chomsky e suas respectivas máqu...

Acerca das características dos problemas decidíveis e indecidíveis e das diferentes linguagens da hierarquia de Chomsky e suas respectivas máquinas reconhecedoras, analise as a�rmações a seguir e assinale a falsa. Seja G1 qualquer gramática irrestrita e G2 seja qualquer gramática regular, então L(G11) ∩ L(G22) = ∅, é indecidível. Nenhum procedimento computacional é considerado um algoritmo a menos que seja representado pela máquina de Turing. Dadas duas gramáticas livres de contexto G1 e G2, é indecidível se L(G1) = L(G2). O problema da parada de uma máquina de Turing é indecidível. É possível construir uma máquina de Turing que aceita qualquer cadeia de comprimento par.
I) Entra em loop in�nito para cadeias em L.
II) Aceita L.
III) Rejeita L.
IV) Resolve o problema em um tempo de execução polinomial.
V) Resolve o problema da Parada.
I, II e III.
III, IV e V.
I, III e V.
II e III.
IV e V.