Teoria da Computação (LEIC-Alameda)

Sumários das aulas práticas

Turma T2

Docente:  Ricardo Gonçalves
Horário: 6a feira, sala V125

P01-10 Out
Construção de AFD's : Exercícios 1.1.1, 1.1.4 a), 1.1.5 a), 1.1.6 a), 1.1.8 a). Exercício de avaliação 1. Enunciado e resolução: [pdf], [ps]

P02-17 Out
Verificação de aceitação de palavras por autómatos. Propriedades de fecho de linguagens regulares. Exercícios 1.1.17a), 1.1.17b), 1.2.7, 1.2.9, 1.2.11, 1.2.10. Exercício de avaliação 2. Enunciado e resolução: [pdf], [ps]

P03-24 Out
Propriedades de fecho de linguagens regulares - Intersecção: exercícios 1.2.4, 1.2.5, 1.2.14. Algoritmo APEPD: exercício 1.3.3 (parcialmente resolvido). Exercício de avaliação 3. Enunciado e resolução: [pdf], [ps]

P04-31 Out
Equivalência e minimização de autómatos: exercícios 1.3.12 a), b), 1.3.2, 1.3.7. Exercício de avaliação 4. Enunciado e resolução: [pdf], [ps]

P05-7 Nov
Teste de igualdade de linguagens: exercício 1.3.6. Construção de AFND's e verificação de aceitação de palavras por AFND's: exercício 1.5.2 a) e b), 1.5.3, 1.5.4 e 1.5.5. Exercício de avaliação 5. Enunciado e resolução: [pdf], [ps]

P06-14 Nov
Passagem de AFND a AFD: exercícios 1.5.5 b), 1.5.10 c). Construção de GR's e demonstração de sequência numa GR: exercícios 2.1 a) e b), 2.6 c), g) e j).
Exercício de avaliação 6. Enunciado e resolução: [pdf], [ps]

P07-21 Nov
Expressões regulares: exercícios 3.1, 3.4 d), e), g) e j), 3.9 a) e d), 3.10 a) e b). Passagem de gramática regular a expressão regular: exercícios 4.1 a) e b), 4.3 a), 4.4 a)
Exercício de avaliação 7. Enunciado e resolução: [pdf], [ps]

P08-28 Nov
Passagem de a.f.n.d. a gramática regular e passagem de gramática regular a a.f.n.d.: 4.6 b), 4.8 a), 4.15 a) e b). Passagem de expressão regular a autómato finito não determinista com movimentos epsilon: 4.21 d) e f), 4.22 c). Exercício de avaliação 8. Enunciado e resolução: [pdf], [ps]

P09-5 Dez
Realização de fluxogramas a partir de programas URM e indicação de funções de diferentes aridades calculadas por esses programas: 1.1.e e 1.1.d. Verificação de que uma função é URM-computável: 1.2.d e 1.2.c. Verificação de que um predicado é URM-decidivel: 1.3.h. Exercício de avaliação 9. Enunciado e resolução: [pdf], [ps]

P11-19 Dez
Exercícios sobre as funções pi, xi, beta, tau: 3.1.a pi(2,4), 3.1.b pi-1(31) e pi-1(47), 3.1.c xi(1,2,1), 3.1.d xi-1(19), 3.1.e beta(Z(5)), beta(S(5)), beta(T(3,4)) e beta(J(2,1,2)), 3.1.f beta-1(25), beta-1(34) e beta-1(79), 3.1.g tau(1,2,3) e tau(0,2,1), 3.1.h tau-1(129). Obtenção do número de Godel correspondente a um programa URM: 3.2.d e 3.2.f. Programa URM correspondente a um número de Godel: 3.3.p e 1407. Exercício de avaliação 10. Enunciado e resolução: [pdf], [ps]