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.