Lema de bombeamento para linguagens livres de contexto e máquinas de Turing.
4 Novembro 2020, 09:30 • André Souto
Motivação para o lema de bombeamento para linguagens livres de contexto.
Enunciado do lema de bombeamento para linguagens livres de contexto.Esquisso da prova.
Exemplos de uso.
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.
A aula foi dada em regime síncrono não presencial com transmissão via Zoom.