ID 1348753 Banca CESPE / CEBRASPE Órgão INMETRO Ano 2010 Provas CESPE - 2010 - INMETRO - Pesquisador Tecnologista em Metrologia e Qualidade - Informática Aplicada à Metrologia Legal Disciplina Algoritmos e Estrutura de Dados Assuntos Algoritmos Estrutura de Dados Grafos Lógicas de Programação Acerca das linguagens formais e dos autômatos, assinale a opção correta. Alternativas A máquina de Turing capaz de simular outras máquinas de Turing é uma Turing completa, chamada máquina de Turing universal, capaz de calcular qualquer função recursiva, decidir qualquer linguagem recursiva e aceitar qualquer linguagem enumeravelmente recursiva. Os autômatos finitos consistem na idealização de um computador capaz de acessar uma quantidade limitada de processos, o que restringe o processamento de informações de forma paralela; portanto, computadores desse gênero têm sua utilização limitada a aplicações simples, como, por exemplo, controlar elevadores ou portas automáticas. Nos autômatos de pilha, existe uma estrutura de controle, que representa os estados e as funções de transição, e um input, que o autômato lê da esquerda para a direita, uma casa de cada vez, atualizando a estrutura de controle. Os autômatos de pilha são modelos com uma quantidade de memória finita. Por sua vez, um autômato finito, apesar da limitada capacidade de processamento, por meio de uma pilha, consegue acessar a uma quantidade infinita de memória. Os autômatos de pilha correspondem a um modelo mais poderoso que as máquinas de Turing, visto que permitem fazer várias operações pop sem perder informações. Responder Comentários Gabarito A Máquina de Turing é um dispositivo teórico conhecido como máquina universal, que foi concebido pelo matemático britânico Alan Turing (1912-1954), muitos anos antes de existirem os modernos computadores digitais (o artigo de referência foi publicado em 1936). Num sentido preciso, é um modelo abstrato de um computador, que restringe-se apenas aos aspectos lógicos do seu funcionamento (memória, estados e transições), e não a sua implementação física. Numa máquina de Turing pode-se modelar qualquer computador digital. Turing também envolveu-se na construção de máquinas físicas para quebrar os códigos secretos das comunicações alemãs durante a Segunda Guerra Mundial, tendo utilizado alguns dos conceitos teóricos desenvolvidos para o seu modelo de computador universal. "Retroceder Nunca Render-se Jamais !" Força e Fé ! Fortuna Audaces Sequitur !