Apresentação da disciplina

Apresentação da disciplina

Conceitos matemáticos básicos

Em cada aula é definido o plano de trabalho autónomo prévio utilizando a seguinte bibliografia disponível na biblioteca do ISCTE-IUL:

[Santos 2013] F. Santos, Teoria da Computação – Folhas de Apoio, ISCTE-IUL, 2013.

[Santos 2019] F. Santos, Teoria da Computação – Exercícios, ISCTE-IUL, 2019.

[Martin 2011] J. Martin, Introduction to Languages and the Theory of Computation, McGraw-Hill, (4ª edição) 2011.

Resolução de exercícios - Conceitos matemáticos básicos

Resolução [Santos 2019] 1, 2

Definições indutivas e recursivas; Conceitos Básicos de Linguagens

Leitura [Martin 2011] cap 1.4, 1.5

Lógica e Técnicas de Prova

Leitura [Martin 2011] cap 1.1, 1.6

Resolução de exercícios - Lógica e Técnicas de Prova

Resolução [Santos 2019] 3, 4, 5, 6, 7

Linguagens Regulares e Expressões Regulares

Leitura [Martin 2011] cap 3.1

Autómatos Finitos Deterministas

Leitura [Martin 2011] cap 2.1

Resolução de exercícios - Autómatos Finitos Deterministas

Resolução [Santos 2019] 8, 9

Combinação de autómatos para reconhecimento de algumas linguagens regulares

Leitura [Martin 2011] cap 2.2

Resolução de exercícios - Combinação de autómatos

Resolução [Santos 2019] 10

Autómatos Finitos Não Deterministas

Leitura [Martin 2011] cap 3.2

Autómatos Finitos Determinísticos equivalentes a Autómatos Finitos Não Deterministas

Leitura [Martin 2011] cap 3.3

Resolução de exercícios - Autómatos Finitos Determinísticos equivalentes a Autómatos Finitos Não Deterministas

Resolução [Santos 2019] 11, 12

Autómatos Finitos Não Deterministas com movimentos-/\

Leitura [Martin 2011] cap 3.2

Autómatos Finitos Não Deterministas equivalentes a Autómatos Finitos Não Deterministas com movimentos-/\

Leitura [Martin 2011] cap 3.3

O teorema de Kleene

Leitura [Martin 2011] cap 3.4

Resolução de exercícios - O teorema de Kleene

Resolução [Santos 2019] 13, 14, 15, 18

Simplificação de Autómatos Finitos

Leitura [Martin 2011] cap 2.6

Resolução de exercícios - Simplificação de Autómatos Finitos

Resolução [Santos 2019] 19, 20, 21

Limites Computacionais dos Autómatos Finitos

Leitura [Martin 2011] cap 2.4; Resolução [Santos 2019] 22

Linguagens Livres de Contexto e Gramáticas Livres de Contexto

Leitura [Martin 2011] cap 4.1

Linguagens Livres de Contexto e Gramáticas Livres de Contexto (continuação)

Leitura [Martin 2011] cap 4.2 pp 134-135

Resolução de exercícios - Linguagens Livres de Contexto e Gramáticas Livres de Contexto

Resolução [Santos 2019] 23, 24, 25

As Linguagens Regulares são Livres de Contexto

Leitura [Martin 2011] cap 4.2 pp 136-138

Gramáticas Regulares

Leitura [Martin 2011] cap 4.3, 4.4

Resolução de exercícios - Gramáticas Regulares

Resolução [Santos 2019] 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39

Autómatos de Pilha

Leitura [Martin 2011] cap 5.1

Aceitação por estado de aceitação vs Aceitação por pilha vazia; A equivalência entre os dois tipos de aceitação

Leitura [Martin 2011] cap 5.2

Resolução de exercícios - Autómatos de Pilha

Resolução [Santos 2019] 40, 41, 42, 43

Autómatos de Pilha equivalentes a Gramáticas Livres de Contexto

Leitura [Martin 2011] cap 5.3

Resolução de exercícios - Autómatos de Pilha equivalentes a Gramáticas Livres de Contexto I

Resolução [Santos 2019] 44

Resolução de exercícios - Autómatos de Pilha equivalentes a Gramáticas Livres de Contexto II

Resolução [Santos 2019] 45

Gramáticas Livres de Contexto: Formas Normais

Leitura [Martin 2011] cap 4.5

Limites computacionais dos Autómatos de Pilha

Leitura [Martin 2011] cap 6.1; Resolução [Santos 2019] 42

Máquinas de Turing e Tese de Church-Turing

Leitura [Martin 2011] cap 7.1, 7.2, 7.6