Aula Prática – Análise de Computabilidade e Complexidade de Algoritmos
Relatório de Aula Prática sobre a criação de uma Máquina de Turing determinística para reconhecer a linguagem L = {aⁿbⁿ | n ≥ 0}. O material contempla estados, transições, testes com palavras aceitas e rejeitadas e a organização da entrega em PDF.
Roteiro de Aula Prática: Análise de Computabilidade e Complexidade de Algoritmos
Esta atividade prática aborda a construção de uma Máquina de Turing determinística capaz de reconhecer uma linguagem formal. O conteúdo pertence à Unidade 1 – Teoria da Computabilidade: Programas e Máquinas, com foco no estudo de máquinas, estados, transições e aceitação de linguagens.
Objetivo da atividade
Compreender os conceitos e as características de uma Máquina de Turing, relacionando seu funcionamento com a aceitação de uma linguagem. O aluno deverá analisar os elementos do modelo computacional e organizar corretamente os estados e as regras de transição.
Atividade proposta
O roteiro solicita o desenvolvimento de uma Máquina de Turing determinística para reconhecer a linguagem L = {anbn | n ≥ 0}. Essa linguagem contém palavras formadas por uma quantidade de símbolos a seguida da mesma quantidade de símbolos b.
A solução deve considerar a fita dividida em células, o cabeçote responsável pela leitura e escrita, um conjunto finito de estados e uma função de transição. Para controlar o processamento, podem ser utilizados os símbolos de entrada a e b, símbolos marcados como A e B e o símbolo de espaço vazio.
Procedimentos solicitados
- Analisar as características e os componentes da Máquina de Turing.
- Criar um modelo teórico baseado em estados e transições.
- Garantir que a máquina construída seja determinística.
- Testar palavras que pertencem à linguagem, como aaabbb.
- Testar palavras que não pertencem à linguagem, como aabbb, abb e aab.
- Verificar o comportamento da máquina até o estado de aceitação ou rejeição.
O que deve aparecer no desenvolvimento
O relatório deve apresentar a Máquina de Turing criada, com seus estados, alfabeto da fita, regras de transição, movimentação do cabeçote e critério de aceitação. A lógica precisa demonstrar como cada símbolo a é relacionado a um símbolo b, como os símbolos já processados são marcados e como a máquina identifica entradas válidas e inválidas.
Entrega da aula prática
Ao final, deverá ser entregue um arquivo em PDF contendo a imagem da Máquina de Turing desenvolvida. Conforme o roteiro, o arquivo final não pode ultrapassar 2 MB.
Produto em preparação: o arquivo resolvido será disponibilizado posteriormente.
