automatos

Linguagens Formais e Autômatos

1

Autômatos e Linguagens formais

A teoria dos autômatos é o estudo dos dispositivos abstratos de computação, isto é, máquinas. Antes de existirem computadores como os atuais, na década de 1930 A. Turing iniciou o estudo de máquina abstrata, estas tinham as mesmas características dos computadores atuais, isto no que tange aos cálculos. O objetivo de Turing era o de descrever com exatidão o que a maquina de calcular poderia ou não fazer, os seus limites; suas conclusões não se aplicam somente as maquinas de Turing abstratas, mas aos computadores atuais.
Nas décadas de 1940 e 1950, tipos de máquinas mais simples, as quais foram denominamos de autômatos finitos, estas foram estudadas por vários pesquisadores, tais autômatos foram projetados inicialmente para modelar a função do cérebro, mostrando-se extremamente úteis para uma grande variedade de outros propósitos. Simultaneamente no final da década de 1950, o lingüista N. Chomsku deu início ao estudo de gramáticas formais. As gramáticas não são estritamente máquinas, porém têm estreito relacionamento com os autômatos abstratos, atualmente servindo como base de vários componentes de software, incluindo algumas partes dos compiladores.
Em 1969, S. Cook estende o estudo de Turing, este consegue separar os problemas que podem ser resolvidos de uma forma eficiente por computadores, e os que podem ser resolvidos, mas, não de uma forma eficiente, isto é, levariam tanto tempo que os computadores seriam inúteis para solucionar todas as instâncias do problema.
Os problemas da ultima classe que citamos denominam-se intratáveis ou ainda NP-difíceis. Os desenvolvimentos teóricos têm relação direta com o que os cientistas da computação fazem hoje. O conceito da maquina de
Turing ajudam então a entender o que podemos esperar de um software.
Em particular, a teoria dos problemas intratáveis permite deduzir se temos chance, de quando estamos diante de um problema ser