Teoria da Computação (LEIC-Alameda)

Sumários das aulas teóricas

Turmas 10101, 10102 e 10103

Docente: Paula Gouveia
Horário: 3ªfeira, 10h-11h, FA3; 4ªfeira, 10h-11h, GA2; 5ªfeira, 10h-11h, GA2

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

T02-1Out
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-2Out
Mais exemplos de autómatos finitos deterministas.

T04-7Out
Definição algébrica de autómato finito determinista (ps, pdf). 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, funções totais e funções definidas por recursão. Função transição de autómato finito determinista (início).

T05-8Out
Função transição de autómato finito determinista (conclusão). Exemplos. Sequência aceite por autómato finito determinista. Linguagem reconhecida por autómato finito determinista. Linguagem regular.

T06-9Out
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).

T07-14Out
Esboço da prova das alínaeas (a), (c) e (d) da Proposição enunciada na aula anterior.

T08-15Out
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). Estados produtivos, estados relevantes e estados inúteis.

T09-16Out
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, descrição e exemplos de aplicação (início).

T10-21Out
Algoritmo de procura exaustiva de pares de estados distinguíveis (conclusão). Esboço da prova de correcção do algoritmo.

T11-22Out
Mais um exemplo de aplicaçã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.

T12-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.

T13-28Out
Autómatos finitos não deterministas (ps,pdf). Definição e exemplos. Função de transição em autómatos finitos não deterministas (início).

T14-29Out
Função de transição em autómatos finitos não deterministas (conclusão). 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).

T15-30Out
Conclusão da aula anterior. Exemplo de aplicação. Esboço da prova da proposição "A linguagem {0^n1^n: n>=0} não é regular" (início).

T16-4Nov
Conclusão da aula anterior. Descrição informal de um autómato de pilha que reconhece a linguagem {0^n1^n: n>=0}. Gramáticas: motivação.

T17-5Nov
Gramáticas. 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.

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

T19-11Nov
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. Expressões regulares (ps,pdf): motivação.

T20-12Nov
Expressões regulares: definição; conjunto denotado por expressão regular. Exemplos. Equivalência de expressões regulares. Alguns exemplos.

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

T22-18Nov
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.

T23-19Nov
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.

T24-20Nov
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.

T25-25Nov
Computabilidade: motivação e breve introdução histórica. Modelos alternativos no estudo da computabilidade (ps,pdf). Postulado de Church-Turing. 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 e comandos sucessor.

T26-26Nov
Comandos da máquina URM: comandos tranferência, comandos salto. Exemplos de programas para a máquina URM: o programa que calcula a função binária que a x e y faz corresponder x+y.

T27-27Nov
Programa normalizado. 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: (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; (iii) o programa que calcula a função binária que a x e y faz corresponder o respectivo produto (usando o oráculo SUM). Preenchimento dos inquéritos pedagógicos.

T28-2Dez
Noção informal de computação finita e de computação infinita de programa. Notações. Função URM-computável. 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-3Dez
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-4Dez
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-11Dez
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-17Dez
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-18Dez
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