automatos

Introdução:

A teoria de autômatos é o estudo de computadores abstratos, também chamados de “máquinas”. Em 1930, antes de existirem computadores, A. Turing desenvolveu uma máquina abstrata que tinha todas as características dos computadores atuais, ao menos no que se refere ao quanto eles poderiam calcular. O objetivo de Turing era descrever com exatidão o que uma máquina de computação seria e o que ela não seria capaz de fazer. As conclusões de Turing se aplicam não apenas a sua máquina, mas também as máquinas reais de hoje.
Na década de 1940 e 1950, tipos de máquinas simples, que hoje são chamados de “autômatos finitos”, foram estudados por diversos pesquisadores. No final dos anos 50, o linguista N. Chomsky iniciou o estudo de “gramáticas” formais. Essas gramáticas têm um relacionamento estreito com os autômatos abstratos e hoje servem como base de importantes componentes de software, incluindo parte dos compiladores.
Em 1969, S. Cook estendeu o estudo de Turing do que podia e não podia ser calculado. Ele conseguiu separar os problemas que podem ser resolvidos de forma eficiente por computadores daqueles que poderiam em princípio ser resolvidos, mas que na prática levam tanto tempo para serem solucionados que os computadores são inúteis para solucioná-los. Tais problemas são chamados “intratáveis” ou “NP-difíceis” (NP-Hard). Mesmo com a melhoria exponencial na velocidade dos computadores (Lei de Moore) é muito pouco provável que haja impacto significativo na habilidade de resolver grandes instâncias de problemas intratáveis.
Todos esses desenvolvimentos teóricos têm ligação direta com o que os cientistas da computação fazem hoje. Por exemplo: a teoria dos problemas intratáveis nos permite deduzir se ao encontrar um problema temos chance de conseguir construir um programa para resolvê-lo (porque ele não é intratável) ou se teremos de descobrir algum modo de contornar o problema intratável. Formalmente, um autômato definido como sendo um modelo