Decidibilidade
21 Novembro 2017, 09:30 • Ana Respicio
O problema da igualdade das linguagens geradas por duas GIC não é computacionalmente resolúvel.
Qualquer linguagem independente do contexto é decidível. Prova.
Relação entre classes de linguagens e os respetivos modelos computacionais.
O problema de aceitação por uma máquina de Turing não é computacionalmente resolúvel.
A liguagem A_TM é Turing-reconhecível. Prova.
Estudar: Sipser cap 4.Praticar: Folha de exercícios 8.