Linguagens formais e compiladores

Universidade Federal de Santa Catarina
Centro Tecnológico

Departamento de Informática e de Estatística

LINGUAGENS FORMAIS E COMPILADORES

(Prof. Olinto José Varela Furtado)

Capítulo I – Introdução

I.1 - Introdução a Compiladores I.2 - Introdução a Teoria da Computação I.3 - Introdução a Teoria das Linguagens Formais

I.1 – Introdução a Compiladores

I.2 - Introdução a Teoria da Computação

O Que é Teoria da Computação? A Teoria da Computação pode ser vista como um guia (um roteiro) que nos orienta no sentido de informar o que pode e o que não pode ser efetivamente computável, explicando porque, de que forma e com que complexidade. Neste sentido, a Teoria da Computação classifica os problemas computacionais em três classes: a) Problemas Indecidíveis (ou impossíveis de serem solucionados); b) Problemas Intratáveis (possíveis com recursos ilimitados, porém impossíveis com recursos limitados); c) Problemas Tratáveis (possíveis de serem solucionadas com recursos limitados).

Esta classificação engloba problemas de toda a natureza, envolvendo desde problemas clássicos que fundamentam a teoria da computação até problemas (ou instâncias de problemas) práticos da ciência da computação, tais como: 1 – Existe programa para solucionar um determinado problema? 2 – Qual o poder de expressão de um determinado modelo de especificação? 3 – Dado um programa qualquer, ele sempre tem parada garantida? 4 – Dois programas P1 e P2 são equivalentes entre si? 5 – Uma determinada solução é a melhor solução para um dado problema? 6 – Qual o significado de um determinado programa? 7 – Dado um programa qualquer, este programa está correto?

Esta lista poderia ser expandida e detalhada, contudo, seu objetivo é enfatizar a abrangência da teoria da computação. Dos tópicos aqui listados, complexidade (5), semântica (6) e correção/construção (7), costumam ser tratados