Sumários

Decidibilidade

29 Novembro 2022, 10:30 • Ana Respicio

Folha 4 exercícios 1, 2, 7a, 10, 11.

Problemas decidíveis relacionados com linguagens regulares: problema de testar se uma expressão regular denota uma palavra, problema da aceitação de uma dada palavra por um autómato finito não determinista, problema da vacuidade da linguagem de um autómato finito determinista, e problema da equivalência entre dois autómatos finitos deterministas.

Problemas decidíveis relacionados com linguagens independentes do contexto: problema de determinar se uma gramática independente do contexto gera uma determinada palavra, problema de determinar se uma se uma gramática independente do contexto gera a linguagem vazia.

Sipser até Teorema 4.8 (inclusive e sem prova).

Decidibilidade.

22 Novembro 2022, 09:30 • Ana Respicio

A tese de Church Turing: Terminologia para descrever Máquinas de Turing. Codificação de objetos. Codificação de um grafo. O problema de decidir se um grafo direcionado é conexo é decidível.

Sipser, Cap 3, secção 3.

Decidibilidade: Introdução. Linguagens decidíveis. Problemas decidíveis relativos a Linguagens Regulares. O problema de testar se um Autómato Finito Determinista aceita uma dada palavra é decidível.

Sipser, Cap 4, secção 1.

Lema do bombeamento

28 Outubro 2022, 11:30 • Diana Filipa de Pinho Costa

Exercícios 29, 31 b) g) 32, 34 f) da Folha 1.

Lema do bombeamento

28 Outubro 2022, 08:00 • Diana Filipa de Pinho Costa

Exercícios 29, 31 b) g) 32, 34 f) da Folha 1.