Teoria da Computação (LEIC-Alameda)

Sumários das aulas teóricas

Turmas 10104, 10105 e 10106

Docente: Paula Gouveia
Horário: 3ªfeira, 9h-10h, FA1; 5ªfeira, 8h-9h, FA1; 6ªfeira, 10h-11h, GA3

T01-30Set
Apresentação: conteúdo, bibliografia e avaliação

T02-2Out
Autómatos finitos deterministas. Exemplos de aplicações (e.g. processadores de texto). Exemplos de autómatos (representação através de um grafo orientado e etiquetado).

T03-3Out
Mais exemplos de autómatos finitos deterministas. Definição algébrica (ps, pdf). Alguns comentários relativos a funções, funções totais e não totais.

T04-7Out
Fecho de Kleene de um conjunto, comprimento de sequência e concatenação de sequências. Linguagem sobre um alfabeto. Alguns comentários relativos a funções definidas por recursão. Função transição de autómato finito determinista. Exemplos.

T05-9Out
Sequência aceite por autómato finito determinista. Linguagem reconhecida por autómato finito determinista. Linguagem regular. Proposição (ps,pdf): a classe das linguagens reconhecidas por autómatos finitos deterministas com o mesmo vocabulário está fechada para as operações de (a) intersecção, (b) complementação, (c) união, (d) diferença, (e) fecho de Kleene, (f) concatenação. Exemplos de aplicação. Esboço da prova da alínea (b) (início).

T06-10Out
Esboço da prova da alínea (b) (conclusão). Esboço da prova das alíneas (a) e (c).

T07-14Out
Esboço da prova da alínea (d). Proposição (ps,pdf): dado um autómato finito determinista D existem algoritmos que permitem determinar se são ou não verdadeiras as afirmações seguintes: (a) a linguagem reconhecida por D é vazia, (b) D reconhece todas as palavras sobre o seu alfabeto, (c) a linguagem reconhecida por D está contida na linguagem reconhecida por um outro autómato finito determinista D' dado, (d) a linguagem reconhecida por D é igual à linguagem reconhecida por um outro autómato finito determinista D' dado, (e) existe um autómato finito determinista D' tal que a linguagem reconhecida por D é igual à linguagem reconhecida por D' e D' tem menos estados que D. Esboço das provas das alíneas (a), (b) e (c).

T08-16Out
Estados produtivos, estados relevantes e estados inúteis. Estados equivalentes e estados distinguíveis: motivação e definição. Algoritmo de procura exaustiva de pares de estados distinguíveis (ps,pdf): motivação e descrição (início).

T09-17Out
Algoritmo de procura exaustiva de pares de estados distinguíveis (conclusão). Exemplos de aplicação.

T10-21Out
Esboço da prova de correcção do algoritmo de procura exaustiva de pares de estados distinguíveis. Algoritmo de teste à igualdade das linguagens reconhecidas por dois autómatos finitos deterministas. Exemplo de aplicação.

T11-23Out
Algoritmo de minimização de autómatos finitos deterministas (relativamente ao número de estados): motivação e descrição. Exemplo de aplicação.

T12-24Out
Autómatos finitos não deterministas (ps,pdf). Definição e exemplos.

T13-28Out
Função de transição em autómatos finitos não deterministas. Exemplos. Linguagem reconhecida por um autómato finito não determinista. Equivalência de autómatos finitos deterministas e não deterministas (ps,pdf). Proposição: se D é um autómato finito determinista, então existe um autómato finito não determinista A tal que a linguagem reconhecida por A é igual à linguagem reconhecida por D. Esboço da prova da proposição. Proposição : se A é um autómato finito não determinista, então existe um autómato finito determinista D tal que a linguagem reconhecida por A é igual à linguagem reconhecida por D. Esboço da prova da proposição (início).

T14-30Out
Função de transição em autómatos finitos não deterministas (conclusão). Linguagem reconhecida por um autómato finito não determinista. Equivalência de autómatos finitos deterministas e não deterministas (ps,pdf). Proposição: se D é um autómato finito determinista, então existe um autómato finito não determinista A tal que a linguagem reconhecida por A é igual à linguagem reconhecida por D. Esboço da prova da proposição. Proposição : se A é um autómato finito não determinista, então existe um autómato finito determinista D tal que a linguagem reconhecida por A é igual à linguagem reconhecida por D. Esboço da prova da proposição.

T15-31Out
Esboço da prova da proposição "A linguagem {0^n1^n: n>=0} não é regular". Referência informal ao lema da bombagem para linguagens regulares. Descrição informal de um autómato de pilha que reconhece a linguagem {0^n1^n: n>=0}.

T16-4Nov
Gramáticas: motivação, definição (ps,pdf). Denotação compacta do conjunto das produções de uma gramática. Demonstração em gramática. Linguagem gerada por uma gramática. Exemplos.

T17-6Nov
Gramática independente do contexto e gramática regular. Exemplos.

T18-7Nov
Proposição (ps,pdf): Para cada autómato finito determinista D (não determinista A) existe uma gramática regular G tal que a linguagem reconhecida por D (A) é igual à linguagem gerada por G. Esboço da prova da proposição. Proposição (ps,pdf): Para cada gramática regular G existe umautómato finito não determinista A tal que a linguagem reconhecida por A é igual à linguagem gerada por G. Esboço da prova da proposição.

T19-11Nov
Expressões regulares (ps,pdf). Motivação. Definição. Conjunto denotado por expressão regular. Exemplos.

T20-13Nov
Equivalência de expressões regulares. Exemplos.

T21-14Nov
Proposição (ps,pdf): a linguagem gerada por uma gramática regular é denotada por uma expressão regular.
Técnicas de resolução de equações às linguagens - regra R. Exemplos.

T22-18Nov
Autómato finito não determinista com movimentos épsilon. Definição(ps,pdf). Conceito de fecho-épsilon de um estado. Proposição(ps,pdf): Para cada autómato finito não determinista com movimentos épsilon A existe um autómato finito não determinista sem movimentos épsilon A' que reconhece exactamente a linguagem reconhecida por A. Esboço da prova.

T23-22Nov
Proposição(ps,pdf): Para cada expressão regular existe um autómato finito não determinista com movimentos épsilon A tal que a linguagem denotada pela expressão é a linguagem reconhecida por A. Esboço da prova: algoritmo de construção do autómato por indução na complexidade das expressões regulares.

T24-21Nov
Computabilidade: motivação e breve introdução histórica. Modelos alternativos no estudo da computabilidade (ps,pdf). Postulado de Church-Turing.

T25-25Nov
A máquina URM (Unlimited Register Machine) (ps,pdf). Memória da máquina URM: registos e valores. Comandos da máquina URM: comandos zero, comandos sucessor, comandos tranferência, comandos salto. Exemplo de programa para a máquina URM: o programa que calcula a função binária que a x e y faz corresponder x+y.

T26-27Nov
Programa normalizado. Exemplos de programas para a máquina URM: (i) o programa que calcula a função unária que a x faz corresponder x-1 se x é maior que 0 e 0 caso contrário; (ii) o programa que calcula a função binária que a x e y faz corresponder x-y se x é maior ou igual a y e 0 caso contrário.

T27-28Nov
Algumas observações sobre a sintaxe usada no emulador, incluindo referência ao comado HALT[] e à utilização de oráculos. Exemplos de programas para a máquina URM: o programa que calcula a função binária que a x e y faz corresponder o respectivo produto (usando o oráculo SUM). Noção informal de computação finita e de computação infinita de programa. Notações. Função URM-computável. Preenchimento dos inquéritos pedagógicos.

T28-2Dez
Função de aridade n calculada por um programa. Predicados. Função característica de um predicado. Predicados decidíveis. Prova de que o predicado unário sobre os naturais "x é par" é decidível.

T29-4Dez
Conjuntos I e P de todos os comandos URM e de todos os programas URM, respectivamente. Godelização de programas URM (ps,pdf): as bijecções pi, xi e beta. Exemplos.

T30-5Dez
Godelização de programas URM (continuação): as funções inversas de pi xi e beta. Exemplos.

T31-9Dez
Godelização de programas URM (conclusão): as bijecções tau e gama e respectivas inversas. Exemplos.

T32-10Dez
Definição de P_n, fi_n_m, W_n_m e de E_n_m. Proposição : Existe uma função natural unária e total que não é URM-computável. Prova da proposição. Problema da paragem: formulação informal. Prova informal da não decidibilidade do problema da paragem.

T33-12Dez
Proposição : O problema da paragem não é decidível. Prova da proposição. Proposição : O predicado 'm pertence a E_n' não é decidível. Proposição : Seja g uma função unária computável. O predicado 'fi_n=g' não é decidível. Proposição : O predicado 'fi_n=fi_m' não é decidível. (Algumas notas (ps,pdf) sobre estes assuntos).

T34-16Dez
Um outro modelo de computabilidade: a classe das funções parciais recursivas (ps,pdf - Nota: neste semestre foram apenas leccionados os assuntos expostos na seccão 1). Funções atómicas (Z, S, U(n,i)). Definição de uma função por composição. Exemplos. Definição de uma função por recursão primitiva (início).

T35-18Dez
Definição de uma função por recursão primitiva. Exemplos de funções definidas por recursão (primitiva): h(x)=x!, h(x)=x^2, h(x)=x mónus 1.

T36-19Dez
Definição de uma função por recursão primitiva (conclusão). Exemplos de funções definidas por recursão primitiva: h(x,y)=x+y, h(x,y)=xy, h(x,y)=x^y. A função h(x,y)=x+y é função parcial recursiva: construção de h a partir de funções atómicas, composição e recursão. h(x,y)=x+y, h(x,y)=xy. Função definida por minimização. Exemplos de funções definidas por minimização: h(x)=raiz quadrada inteira de x, h(x)=quociente da divisão inteira de x por 4.

FIM