Projeto do Compilador - Autômatos Finitos

Os autômatos finitos são uma máquina de estado que pega uma string de símbolos como entrada e muda seu estado de acordo. Autômatos finitos são um reconhecedor de expressões regulares. Quando uma string de expressão regular é alimentada em autômatos finitos, ela muda seu estado para cada literal. Se a string de entrada for processada com sucesso e o autômato atingir seu estado final, ela será aceita, ou seja, a string que acabou de ser alimentada foi considerada um token válido da linguagem em questão.

O modelo matemático de autômatos finitos consiste em:

  • Conjunto finito de estados (Q)
  • Conjunto finito de símbolos de entrada (Σ)
  • Um estado inicial (q0)
  • Conjunto de estados finais (qf)
  • Função de transição (δ)

A função de transição (δ) mapeia o conjunto finito de estado (Q) para um conjunto finito de símbolos de entrada (Σ), Q × Σ ➔ Q

Construção de autômatos finitos

Seja L (r) uma linguagem regular reconhecida por alguns autômatos finitos (FA).

  • States: Estados de FA são representados por círculos. Os nomes dos estados são escritos dentro de círculos.

  • Start state: O estado a partir do qual o autômato começa é conhecido como estado inicial. O estado inicial tem uma seta apontada para ele.

  • Intermediate states: Todos os estados intermediários têm pelo menos duas setas; um apontando para e outro apontando a partir deles.

  • Final state: Se a string de entrada for analisada com sucesso, espera-se que o autômato esteja neste estado. O estado final é representado por círculos duplos. Pode ter qualquer número ímpar de setas apontando para ele e um número par de setas apontando para ele. O número de setas ímpares é um maior do que par, ou seja,odd = even+1.

  • Transition: A transição de um estado para outro ocorre quando um símbolo desejado na entrada é encontrado. Na transição, os autômatos podem passar para o próximo estado ou permanecer no mesmo estado. O movimento de um estado para outro é mostrado como uma seta direcionada, onde as setas apontam para o estado de destino. Se o autômato permanecer no mesmo estado, uma seta apontando de um estado para ele mesmo é desenhada.

Example: Assumimos que FA aceita qualquer valor binário de três dígitos terminando no dígito 1. FA = {Q (q 0 , q f ), Σ (0,1), q 0 , q f , δ}