Hierarquia de Chomsky
Tipos de Linguagens
Linguagens Regulares: Máquina de estados finitos.
Linguagens Livres de Contexto:
Linguagens Dependentes de Contexto:
Linguagens Irrestritas: Linguagem natural (português, inglês, mandarim) é um exemplo.
Máquina de Turing
A Máquina de Turing é uma quíntupla.
Linguagens Recursivas e Recursivamente Enumeráveis
Se uma linguagem é recursiva, então também é recursivamente enumerável.
Hipótese de Church
Pergunta: Por que ela é chamada de Hipótese de Church ao invés de Teorema de Church?
Resposta: A Hipótese de Church não é um resultado matemático e, portanto, não pode ser provado.
Problemas de Decisão
Problema Solucionável
Um problema é dito solucionável ou totalmente solucionável se existe um... Continue a ler "Introdução à Teoria da Computação" »