Aut matos Finitos

Capítulo 2
AUTÔMATOS FINITOS

2.1 Introdução

Um Autômato Finito (AF) é uma máquina que lê uma fita de entrada uma única vez, na qual uma instrução a ser executada é determinada pelos estados da máquina e símbolos da entrada sendo processados.
Os autômatos finitos podem fazer a análise léxica de um compilador, ou seja, verificar se não foi utilizado nenhum símbolo que não pertença ao alfabeto da linguagem, além de identificar os tokens 1 do programa fonte. Além disso, podem ser utilizados para modelar dispositivos que tenham um conjunto finito de entradas e um conjunto finito de ações a serem tomadas. Exemplos: máquina de vender cartão telefônico, máquina de vender refrigerante.
Um autômato finito é um modelo matemático de uma máquina que aceita um conjunto particular de palavras sobre um determinado alfabeto, ou seja, reconhece uma linguagem qualquer. No capítulo 1 foi mostrado que uma linguagem pode ser entendida, grosso modo, como um subconjunto de ∑*. Isto significa que dado um alfabeto qualquer, pode-se combinar os símbolos do mesmo formando um conjunto infinito de palavras.
A criação de uma linguagem formal deve ser realizada em várias etapas, sendo que a primeira delas se constitui na escolha das palavras que farão parte da mesma. Os critérios para a escolha destas palavras pode ser feita de várias formas, como por exemplo, palavras que possuem a propriedade de ter certo prefixo ou sufixo.
Geralmente uma linguagem de programação possui um conjunto de palavras que podem ser classificadas como: palavras reservadas, identificadores, operadores simples e compostos, símbolos de pontuação e constantes numéricas, além dos comentários que, embora não façam parte de nenhum comando da linguagem, podem ser utilizados livremente pelo programador em seus arquivos.
Quando um profissional de TI vai aprender uma nova linguagem, ele primeiro conhece as palavras válidas. Algumas são listadas, como os operadores (<, >, =, * ...) e outras são definidas por um conjunto de