Exercícios folha 4 e 5

5 Novembro 2021, 08:00 • André Souto

Resolução de exercícios da 4ª folha e folha 5 sobre forma normal de Chomsky e autómatos de pilha. 

Gramáticas Livres do Contexto e Autómatos de Pilha

5 Novembro 2021, 08:00 • Paulo Jorge Cunha Vaz Dias Urbano

Exercícios de conversão de Gramáticas Livres do Contexto na sua Forma Normal de Chomski

Uso do Lema de bombeamento para linguagens livres de contexto, Máquinas de Turing

3 Novembro 2021, 09:30 • André Souto

Exemplos de uso do lema de bombeamento.

Prova de que a intersecção e complemento de linguagens livres de contexto pode não ser uma linguagem livre de contexto.

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.

Estudar a secção 2.3 e 3.1 do livro Sipser.

Exercícios folha 4 e 5

3 Novembro 2021, 08:00 • André Souto

Resolução de exercícios da 4ª folha e folha 5 sobre forma normal de Chomsky e autómatos de pilha. 

Exercícios folha 4 e 5

2 Novembro 2021, 10:30 • André Souto

Resolução de exercícios da 4ª folha e folha 5 sobre forma normal de Chomsky e autómatos de pilha.