Relatório Maquina de Turing

UNESPAR – UNIVERSIDADE ESTADUAL DO PARANÁ[pic 1]

CESAR AUGUSTO BELETATTI

MÁQUINA DE TURING

Apucarana

2015

SUMÁRIO

INTRODUÇÃO        

OBJETIVO/JUSTIFICATIVA        

MÁQUINA DE TURING        

EXEMPLOS DE MÁQUINAS DE TURING        

DESIÇÕES DE PROJETO PARA A IMPLEMENTAÇÃO        

∙        ESTRUTURA DE DADOS UTILIZADA        

∙        DENTRE OUTRAS QUESTÕES RELATIVAS À IMPLEMENTAÇÃO        

CONCLUSÃO        

REFERÊNCIAS        

INTRODUÇÃO

Esse software foi desenvolvido para a disciplina de Linguagens Formais e Autômatos, no curso de Ciência da Computação, que constitui em desenvolver um software que diga se a palavra pertence ou não a Maquina de Turing.

OBJETIVO/JUSTIFICATIVA

Este trabalho tem como objetivo criar um algoritmo para o funcionamento de uma Maquina de Turing transdutora e reconhecedora, que a partir de sua descrição formal, o usuário poderá saber se a palavra descrita pertente ou não à linguagem descrita pela Maquina de Turing. E também ajuda na velocidade para descobrir se a palavra pertence ou não.

MÁQUINA DE TURING

A máquina de Turing foi criada por um matemático britânico chamado Allan Turing, muitos anos antes de existir computadores digitais. Consiste em um modelo abstrato de um computador, que se restringe em apenas aspectos lógicos do seu funcionamento (memória, estados e transições) e não a implementação física. Em uma maquina de Turing pode – se modelar qualquer computador digital.

Uma Máquina de Turing consiste em uma fita que é dividida em células, uma adjacente à outra. Cada célula contém um símbolo de algum alfabeto finito. O alfabeto contem um símbolo especial branco e outros símbolos adicionais. As células que ainda não foram escritas são preenchidas com o símbolo branco. Contem um cabeçote, que pode ler e escrever símbolos na fita e mover para direita  e para a esquerda.

Uma Máquina de Turing contem estados, onde há um estado inicial que é onde inicia a Maquina de Turing e um final.

E uma tabela de transição, que diz a máquina que símbolo escreve como mover o cabeçote e qual será seu novo estado.

EXEMPLOS DE MÁQUINAS DE TURING

Máquina de Turing Transdutora

É uma máquina para computar uma função. Aplica uma função sobre o conteúdo inicial da fita e o resultado produzido é lançado na própria fita.

Máquina de Turing Reconhecedora

É uma máquina que processa a palavra de entrada aceitando-a ou rejeitando-a. Neste caso, o conjunto de palavras aceitas corresponde à linguagem descrita pela Máquina de Turing

DESIÇÕES DE PROJETO PARA A IMPLEMENTAÇÃO

        

• ESTRUTURA DE DADOS UTILIZADA

Foi utilizada como estrutura de dados a linguagem Java, como ambiente de desenvolvimento, foi usado o Netbeans, pois foi a ferramenta que encontrei maior facilidade em desenvolver o software, e é uma linguagem fácil de ser compreendida.

...