Sistemas de informação

LICENCIATURA EM ENGENHARIA INFORMÁTICA

TEORIA DA COMPUTAÇÃO

António Dourado Pereira Correia

Advertência. Este documento é um texto de trabalho para apoio ao estudo da cadeira de Teoria da Computação.
Não inclui toda a matéria leccionada na disciplina e naturalmente não dispensa a consulta da bibliografia complementar. O autor agradece qualquer comentário ou sugestão que o tolerante e paciente leitor entenda por bem fazer.

Departamento de Engenharia Informática
Faculdade de Ciências e Tecnologia
Universidade de Coimbra
Setembro 2009

Índice Geral

Capítulo 1. Introdução e definições básicas

1

Capítulo 2. Autómatos finitos

43

Capítulo 3. Expressões regulares, linguagens regulares e gramáticas regulares

115

Capítulo 4. Propriedades das linguagens regulares

153

Capítulo 5. Linguagens livres de contexto

179

Capítulo 6. Simplificação de gramáticas e formas normais

213

Capítulo 7. Autómatos de Pilha

245

Capítulo 8. Propriedades das linguagens livres de contexto

273

Capítulo 9. Máquinas de Touring

299

Teoria da Computação

Capítulo 1 – Introdução e Definições Básicas

CAPÍTULO 1

INTRODUÇÃO E DEFINIÇÕES BÁSICAS

1.1. Introdução

3

1.2. Linguagens formais

3

1.2.1. Alfabetos, cadeias e operações sobre cadeias

5

1.2.2 .Operações de conjuntos sobre linguagens

10

1.3 Gramáticas

17

1.4 Autómatos

30

1.5. Os três paradigmas da computação

37

Bibliografia

42

Anexo

42

LEI/DEI/FCTUC/2009/@ADC

Documento de trabalho

1

Teoria da Computação

LEI/DEI/FCTUC/2009/@ADC

Capítulo 1 – Introdução e Definições Básicas

Documento de trabalho

2

Teoria da Computação

Capítulo 1 – Introdução e Definições Básicas

1.1. Introdução
As ciências da computação, numa interpretação genérica, têm a ver com todos os aspectos relacionados com os computadores e o seu funcionamento. Há no entanto três temas centrais que são delas estruturantes: