Sumários

Resolução de exercícios sobre PDA

12 Novembro 2019, 11:00 • Andreia Mordido

Resolução de exercícios sobre forma normal de Chomsky.

Resolução de exercícios sobre PDA's. Realização de um exercício sobre PDA's para avaliação.

Resolução de exercícios sobre PDA

12 Novembro 2019, 10:30 • André Souto

Resolução de exercícios sobre forma normal de Chomsky.

Resolução de exercícios sobre PDA's.

Realização de um exercício sobre PDA's para avaliação.

Máquinas de Turing

12 Novembro 2019, 09:30 • André Souto

Motivação para o estudo das máquinas de Turing.

A tese de Church-Turing como ponto central da Teoria da computação.

Noção intuitiva de máquina de Turing.

Diferença para os FA e PDA.

Périplo para a definição formal de máquina de Turing.

Exemplos.

Definição formal de máquina de Turing.

Noção de configuração e computação numa máquina de Turing.

Linguagem reconhecível por uma máquina de Turing.

Noção de linguagem Turing-reconhecível.

Máquinas de Turing de decisão.

Noção de linguagem Turing-decidível.

Prova que toda a linguagem Turing-decidível é Turing-reconhecível.

Estudar secção 3.1 do sipser.

Resolução de exercícios sobre PDA

11 Novembro 2019, 08:00 • André Souto

Resolução de exercícios sobre forma normal de Chomsky.

Resolução de exercícios sobre PDA's.

Realização de um exercício sobre PDA's para avaliação.

Exercícios sobre gramáticas livres de contexto

8 Novembro 2019, 11:30 • Andreia Mordido

Resolução de exercícios sobre gramáticas livres de contexto. Definição de linguagem, produção de strings, definição de gramáticas, ambiguidade e forma normal de Chomsky.