Teoria dos Autômatos e Linguagens Formais
aula 13: O autômato bidirecional (pdf, video)
- andando pra frente e pra trás
plano da aula
1. Introdução
- Quem disse que não?
2. O autômato bidirecional
- controlando a movimentação da cabeça de leitura
exemplo 1:
A linguagem das metades
exemplo 2: back-tracking
exemplo 2: back-tracking
3. Andando para trás
- andar para trás é a mesma coisa que andar para frente
4. O autômato vai-e-volta
-
andar pra frente e depois pra trás
é a mesma coisa que só andar uma vez pra frente
5. O autômato volta-e-vai
- ? ? ?
6. O autômato bidirecional
- argumento de simulação
lista de exercícios 13 (pdf)
exercício 1: A linguagem das metades
exercício 2: O autômato bidimensional
exercício 3: O autômato com duas cabeças
↩︎ Voltar