Teoria da Computação
Um percurso para construir linguagens, autómatos e gramáticas, justificar as construções e reconhecer os seus limites.
Uma linguagem especifica quais as entradas válidas. Para aceitar palavras terminadas em , basta guardar um sufixo curto. Para comparar , é preciso recordar uma quantidade sem limite fixado. O percurso constrói esses modelos, justifica as suas respostas e prova onde cada memória deixa de chegar.
Percurso de estudo
- Palavras, linguagens e expressões: distinguir símbolos, palavras e conjuntos, calcular operações e escrever provas por indução.
- Autómatos finitos: escolher estados com significado, construir um DFA e provar o seu invariante.
- NFA e transições vazias: seguir percursos alternativos, calcular fechos e determinizar.
- Converter expressões e autómatos: construção de Thompson e eliminação de estados.
- Propriedades e limites das regulares: produto, decisão, equivalência, minimização e lema da repetição.
- Gramáticas livres de contexto: construir regras, derivar palavras, desenhar árvores e tratar ambiguidade.
- Autómatos de pilha: seguir configurações, distinguir critérios de aceitação e converter entre CFG e PDA.
- Propriedades das livres de contexto: simplificação, CNF, CYK, fecho e lema da repetição.
- Máquinas de Turing e decidibilidade: programar a fita, justificar terminação e distinguir reconhecimento de decisão.
- Complexidade: introdução ao custo dos algoritmos, certificados e reduções polinomiais.
Cada lição liga a problemas de construção, cálculo e prova, com resolução justificada e pistas quando ajudam a escolher um passo. Alguns enunciados são originais; outros adaptam folhas práticas e testes de 2022/23, 2023/24 e 2024/25, e estão assinalados como tal nas páginas de prática. A Cheat sheet reúne condições e procedimentos para consulta depois de estudar.
Para cada construção, escreve primeiro o que cada estado ou variável significa. Depois segue uma palavra aceite, uma rejeitada e a palavra vazia. Por fim, justifica por que todas as entradas recebem a resposta certa. Para uma prova negativa pelo lema da repetição, distingue o que tu escolhes do que tens de cobrir em qualquer decomposição.
Os pré-requisitos são conjuntos, funções, lógica e indução de MD. Quando uma prova falha, confere os quantificadores antes de mudar a construção.
Materiais e edição: base editorial e cobertura
A base é o Moodle de TC de 2024/25, com materiais de Jácome Cunha e Luís Antunes. A apresentação, a introdução e os slides de DFA, NFA, ε-NFA, expressões regulares, linguagens regulares e CFG identificam 2024/25. O Moodle reutiliza também slides de PDA, propriedades de CFL e Turing que identificam 2023/24, e folhas práticas de propriedades de CFL e Turing que identificam 2022/23. Algumas folhas de 2024/25 conservam cabeçalhos de 2023/24 em páginas interiores.
O segundo teste resolvido identifica 13 de junho de 2024, apesar de estar nesse Moodle. Serve para reconhecer tipos de perguntas, como classificar gramáticas, seguir PDA e interpretar tabelas de Turing. Os exercícios destas páginas têm resoluções próprias. Alguns enunciados adaptam tipos de perguntas desse teste e das folhas práticas; cada página de prática distingue exercícios originais de adaptações.
A ficha de 2026/27, consultada novamente em 17 de outubro de 2026, confirma TC no segundo semestre, com 6 ECTS e regência de Nelma Resende Araújo Moreira, mas ainda não apresenta programa nem avaliação. O percurso segue os materiais disponíveis de 2024/25.
O arquivo do Accio acrescenta o primeiro teste de 24/3/2023, de 2022/23, que admite conversão por derivadas, e uma cópia do segundo teste de 11/6/2025, identificado por dentro como 2024/25. Este último motiva problemas de escolha de ramos em PDA, testemunhas para o lema de CFL e compactação de fita. As respostas assinaladas nessa cópia não substituem as provas e cálculos das resoluções. Estes enunciados não confirmam a avaliação de 2026/27.
A ficha preenchida de 2025/26 inclui os mesmos modelos e propriedades. A página de complexidade desenvolve a ligação a computabilidade e custo dos algoritmos; o programa listado centra-se em linguagens formais e introdução às máquinas de Turing. Trata a página de complexidade como extensão: estuda-a depois das máquinas de Turing e não infiras a profundidade da avaliação a partir desta extensão.
Avaliação: regras de 2025/26
A ocorrência de 2026/27 ainda não publica regras. A ficha de 2025/26, consultada em 3 de outubro de 2026, indicava dois testes escritos de 50% cada, mínimo de 6 valores em cada teste, frequência de pelo menos 75% das TP e exame de recurso com peso de 100%. Estas regras pertencem a essa ocorrência; a nova consulta de 8 de outubro não permitiu verificá-las. Confirma as regras da tua edição no SIGARRA e no Moodle antes da prova; os materiais fornecidos não confirmam o regime de 2026/27.
Fontes e bibliografia
Os recursos principais do Moodle são a apresentação, introdução, DFA, NFA, ε-NFA, expressões regulares, propriedades das regulares, CFG, PDA, propriedades de CFL e Turing. O acesso pode exigir autenticação da UP.
A bibliografia indicada pela cadeira é:
- Hopcroft, Motwani e Ullman, Introduction to Automata Theory, Languages, and Computation, edição Pearson de 2014, ISBN 978-1-292-03905-3. Os slides referem também a 3.ª edição de 2007.
- Hopcroft, Motwani e Ullman, Introdução à teoria de autômatos, linguagens e computação, 2003, ISBN 85-352-1072-5.
- Michael Sipser, Introduction to the Theory of Computation, 2.ª edição, 2006, ISBN 0-619-21764-2.
- Thomas Sudkamp, Languages and Machines, 1988, ISBN 0-201-15768-3.
Os textos integrais destes livros não estavam disponíveis para esta revisão. As explicações foram reconstruídas a partir dos slides e folhas práticas disponíveis. O arquivo de xico2001pt/FEUP-TCOM conserva materiais históricos de 2020/21. Os resumos de SofiaViP são uma referência de consulta anterior, sem uma edição atual identificada. Nenhuma destas origens antigas confirma regras da edição atual.