Cronograma 2020.3:
: Entrega da Atividade [1]
: Entrega da Atividade [2.a]
: Entrega da Atividade [2.b]
: 1ª VA escrita
: Entrega da implementação do autômato com pilha (Implementar/codificar a linguagem L = {a^(n)b^(m)c^(n+m) | n, m >= 0})
: Minimização de Autômatos Finitos (dupla1); Lema do Bombeamento para Linguagens Regulares e Livres de Contexto (dupla2)
: Máquina de Post, Problema da Parada e Computabilidade (dupla3); Decidibilidade e Redução de Problemas (dupla4)
: Incompletude de Gödel (dupla5); Computação em DNA (dupla6)
: Computação Quântica (dupla7)
: 2ª VA escrita
: 3ª VA escrita
: Avaliação Final
Atividade [1]: No Gals, defina as expressões regulares capazes de reconhecer...
Dupla 1:
1) Nros. de Telefones no Brasil
2) Placas de Carros Brasileiros
3) ISBN de um livro
4) Endereços IP válidos
Dupla 2:
5) Prefixos de estações de rádio (e.g. 102.3 MHz)
6) Números romanos
7) Número de matrícula da UFRPE
8) Números reais (qualquer notação, incluindo científica)
Dupla 3:
9) Tags HTML (padrão)
10) URL de páginas Web
11) Palavras da Língua Portuguesa
12) Strings de um programa em linguagem “C”
Atividade [2]:
Utilizando a ferramenta JFlap, entregar a solução das seguintes questões das listas abaixo:
a) TC-lista2-autômatos.pdf => 3ª questão, quesitos c, g, h;
b) TC-lista4-AutomatoComPilha.pdf => 6ª questão quesitos a, c, d.
Atividade [3]:
1 Lema do bombeamento para Linguagem Regular e Linguagem Livre de Contexto -
2 Computação em DNA -
3 Decidibilidade e Redutibilidade -
4 Máquina de Post e Problema da Parada -
5 Computação Quântica -
6 Minimização de autômatos -
7 Lâmbda-Cálculo
I - Lema do bombeamento para linguagens Regulares e Livres de Contexto; []
II - Máquina de Post e Problema da Parada, Teoria da Computação: Máquinas Universais e Computabilidade (Tiarajú A. Divério; Paulo Blauth Menezes); []
III - Decidibilidade e Redução de Problemas, pode ser encontrado no livro do Michael Sipser; []
IV - Teoremas da incompletude de Gödel; []
V - Classes de Complexidade (temporal e espacial), pode ser encontrado no livro do Michael Sipser; []
Tempo mínimo: 25 minutos; tempo máximo: 45 minutos.
TODOS devem apresentar e a dupla/trio deve equilibrar o tempo de apresentação para que nenhum dos componentes seja sobrecarregado de conteúdo, ambos devem apresentar em um mesmo período de tempo.
Em toda a apresentação deve ter teoria e prática, com exemplos. Além disso, cada dupla deve trazer 3 questões para seus colegas de classes resolverem.