Linguagens, Autômatos e Computabilidade: Listas de exercícios

Ao longo do curso MAC4722 do primeiro semestre de 2016, referente à teoria da computação, foram propostas algumas listas de exercícios, onde a maioria destes se referiam a exercícios da segunda edição do livro Introduction to the Theory of Computation de Michael Sipser.

Seguem as minhas soluções para os exercícios propostos:

Lista 1 - Capítulo 0: Provas por construção e indução.

• Problema 0.11
• Outros exercícios

Lista 2 - Capítulo 1: Linguagens regulares e autômatos finitos.

• Problema 1.16
• Outros exercícios

Lista 3 - Capítulo 1: Linguagens não regulares.

• Problema 1.46
• Problema 1.49
• Outros exercícios

Lista 4 - Capítulo 2: Gramáticas livres de contexto e autômato de pilha.

• Problema 2.9
• Problema 2.11
• Problema 2.14
• Problema 2.25
• Problema 2.27 a
• Outros exercícios

Lista 5 - Capítulo 2: Lema do bombeamento para gramátitas livres de contexto.

• Problema 2.20
• Problema 2.30 a
• Problema 3.30 d
• Problema 3.32
• Outros exercícios

Lista 6 - Capítulo 3: Máquinas de Turing.

• Problema 3.6
• Problema 3.8
• Problema 3.14
• Problema 3.16