Linguagens formais

Disponível somente no TrabalhosFeitos
  • Páginas : 6 (1290 palavras )
  • Download(s) : 0
  • Publicado : 31 de março de 2013
Ler documento completo
Amostra do texto
GILIARD GODINHO























TRABALHO DE TEORIA DA COMPUTAÇÃO






















CRICIÚMA, NOVEMBRO DE 2009.
GILIARD GODINHO


















TRABALHO DE TEORIA DA COMPUTAÇÃO















Trabalho apresentado à disciplina de Teoria da Computação, solicitado pelaProf. Christine Vieira Scarpato.











CRICIÚMA, NOVEMBRO DE 2009.

1. AUTÔMATO DE PILHA




São formalismos (máquinas) capazes de reconhecer as Linguagens Livres de Contexto, possuem maior poder que os Autômatos Finitos, pois tem um “espaço de armazenamento” extra que é utilizado durante o processamento de uma cadeia. Possui uma pilha que caracteriza umamemória auxiliar onde pode-se inserir e remover informações mesmo poder de reconhecimento das GLC.
[pic]


♦ AP ou AP Não-Determinístico
♦ Fita
Análoga à do Autômato Finito


♦ Cabeça de Fita
Unidade de leitura, possui acessa uma célula da fita de cada vez movimentado-se exclusivamente para a direita, e ainda pode-se testar se leutoda a entrada


♦ Cabeça da Pilha
unidade de leitura e gravação
leitura: move para baixo acessando um símbolo de cada vez (topo) exclui o símbolo lido e pode testar se a pilha está vazia


gravação: move para cima, sendo possível armazenar uma palavra composta por mais de um símbolo neste caso, o símbolo do topo é o mais à esquerda da palavra gravada.♦ Programa ou Função de Transição
• programa
∗ comanda a leitura da fita
∗ comanda a leitura e gravação da pilha
∗ define o estado da máquina














2. Alan Mathison Turing




Alan Mathison Turing nasceu em 23 de junho de 1912 em Londres, filho de um oficial britânico, Julius Mathison e Ethel SaraTuring. Seu interesse pela ciência começou cedo, logo que aprendeu a ler e escrever, distraia-se fatorando números de hinos religiosos e desenhando bicicletas anfíbias.


Em 1928, Alan começou a estudar a Teoria da Relatividade, conhecendo Christopher Morcom, que o influenciou profundamente. Morcom morreu em 1930 e Alan se motivou a fazer o que o amigo não teve tempo, durante anos trocoucorrespondências com a mãe de Morcom a respeito das idéias do amigo e se maravilhou com a possibilidade de resolver problemas com a teoria mecânica quântica.Chegou inclusive a escrever sobre a possibilidade do espírito sobreviver após a morte.


Em 1936, com a idade de 24 anos, Alan M.Turing consagrou-se como um dos maiores matemáticos do seu tempo quando fez antever aos seus colegasque era possível executar operações computacionais sobre a teoria dos números por meio de uma máquina que tivesse embutidas as regras de um sistema formal. Embora propriamente não existisse tal máquina, Turing enfatizou desde o início que tais mecanismos poderiam ser construidos. Sua descoberta abriu uma nova perspectiva no esforço de formalizar a matemática, e, ao mesmo tempo, marcou fortemente ahistória da computação.


Quando a II Guerra Mundial eclodiu, Turing foi trabalhar no Departamento de Comunicações da Gran Bretanha (Government Code and Cypher School) em Buckinghamshire, com o intuito de quebrar o código das comunicações alemãs, produzido por um tipo de computador chamado Enigma. Este código era constantemente trocado, obrigando os inimigos a tentar decodifica-locorrendo contra o relógio. Turing e seus colegas cientistas trabalharam num sistema que foi chamado de Colossus, um enorme emaranhado de servo-motores e metal, considerado um precursor dos computadores digitais.


Durante a guerra, Turing foi enviado aos EUA a fim de estabelecer códigos seguros para comunicações transatlânticas entre os aliados. Supõe-se que foi em Princeton, NJ, que...
tracking img