LEIC - Computabilidade e Linguagens Formais
Aulas teóricas
| Aula | Data | Sumário |
|---|---|---|
| 26 | 2003-06-05 | Diagrama de transição. Linguagem de uma máquina de Turing. Problema da paragem. Técnicas de programação. Extensões e restrições às máquinas de Turing. |
| 25 | 2003-06-03 | Máquinas de Turing. Apresentação e definição formal. Descrição instantânea e computação. Tabelas de transição de estados. |
| 24 | 2003-05-29 | Substituição. Propriedades de fecho das CFLs. CFL e intersecção. Complexidade das conversões. Propriedades de decisão das CFL. Problemas não decidíveis. Indecidibilidade. Problema do teste da saída e prova da sua indecidibilidade. Redução de problemas. Exemplo de uma redução. |
| 23 | 2003-05-27 | Propriedades das CFLs. Simplificação de CFG's. Eliminação de símbolos inúteis. Eliminação de produções anuladoras. Eliminação de produções unitárias. Forma normal de Chomsky. Lema da bombagem para CFL. Provar que uma linguagem não é CFL. |
| 22 | 2003-05-22 | Linguagens dos autómatos de pilha. Equivalência entre aceitação por estado final e por pilha vazia. Equivalência entre CFG e autómatos de pilha. Conversão. |
| 21 | 2003-05-20 | Autómatos de pilha. Definição. Diagramas de transição. Descrição instantânea. Princípios das descrições instantâneas. |
| 20 | 2003-05-15 | Conversão de uma gramática com expressões regulares no corpo para uma CFG. Ambiguidade de uma CFG. Técnicas de desambiguação. Ambiguidade e derivações. Linguagens inerentemente ambíguas. |
| 19 | 2003-05-13 | Árvores de análise. Construção das árvores de análise. A colheita de uma árvore de análise. Equivalência das representações das linguagens sem contexto. Aplicações das CFG: analisadores de linguagens; linguagens de anotação de gramática fixa (HTML) e definível (XML). |
| 18 | 2003-04-29 | Linguagens e gramáticas sem contexto (CFG). Exemplo do palindroma. Definição de CFG. Regras de produção. Inferência recursiva. Derivação. Derivações à esquerda e à direita. A linguagem de uma gramática. Formas frásicas. |
| 17 | 2003-04-24 | Minimização de DFA. |
| 16 | 2003-04-15 | Não houve aula. |
| 15 | 2003-04-10 | Complexidades das conversões entre representações de RL. Propriedades de decisão de RL. Linguagens vazias. Reconhecimento de cadeias. Equivalência de estados. Equivalência de RL. |
| 14 | 2003-04-08 | Propriedades de fecho de uma RL relativas a: operações booleanas, reverso, homomorfismos e homomorfismos inversos. |
| 13 | 2003-04-03 | Miniteste. |
| 12 | 2003-04-01 | Exercícios de aplicação. |
| 11 | 2003-03-27 | Propriedades das linguagens regulares (RL). Linguagens não regulares. O lema da bombagem. Aplicações. |
| 10 | 2003-03-25 | Aplicação das RE. Expressões regulares em UNIX e pesquisa de padrões. Leis algébricas das RE. Associtividade e comutatividade. Elemento neutro e elemento absorvente. Distributividade. Idempotência. Leis que envolvem o fecho. Descoberta de mais leis e teste da concretização. |
| 9 | 2003-03-20 | Equivalência entre os autómatos finitos e as expressões regulares. Dos DFA às RE: métodos da indução nos caminhos e da eliminação de estados. Conversão de RE para ε-NFA. |
| 8 | 2003-03-18 | Expressões regulares (RE). Operadores sobre RE. Construção indutiva de RE. Precedência dos operadores. Exemplos. |
| 7 | 2003-03-13 | Autómatos finitos com transições-epsilon (ε-NFA). Fecho das transições ε. Extensão das transições e linguagens. Eliminação das transições-ε. |
| 6 | 2003-03-11 | Equivalência entre NFAs e DFAs. Conversão de um NFA para um DFA pela técnica de construção de subconjuntos. Casos desfavoráveis da conversão. Estados mortos. Aplicação à pesquisa de texto. |
| 5 | 2003-03-06 | Autómatos finitos não deterministas (NFA). Evolução dos estados. Interpretação do não determinismo. Alterações na função de transição e na sua extensão. Linguagem de um NFA. |
| 4 | 2003-02-27 | Autómatos finitos deterministas (DFA). Processamento de cadeias. Diagramas de transição. Extensão da função de transição. Linguagem de um DFA. |
| 3 | 2003-02-25 | Autómatos finitos. Exemplo motivador com definição de um protocolo. Como ignorar acções. Modelos separados. Interacção. Autómato produto. |
| 2 | 2003-02-20 | Referência histórica. Interesse da Teoria dos Autómatos. Interruptor on-off. Representações estruturais. Conceitos de alfabeto, cadeia, linguagem. Revisão de noções de prova por indução. |
| 1 | 2003-02-18 | Apresentação. Objectivos e conteúdo da disciplina, no contexto do curso. Metodologia e avaliação. |
Docentes: Gabriel David, Cristina Ribeiro