• Autômatos finitos são usados ​​para reconhecer padrões.
• Ele pega a sequência de símbolos como entrada e altera seu estado de acordo. Quando o símbolo desejado é encontrado, ocorre a transição.
• No momento da transição, o autômato pode passar para o próximo estado ou permanecer no mesmo estado.
• Os autômatos finitos têm dois estados, Aceitar estado ou Estado rejeitado . Quando a string de entrada for processada com sucesso e o autômato atingir seu estado final, ele aceitará.

Definição Formal de FA

Um autômato finito é uma coleção de 5 tuplas (Q, ∑, δ, q0, F), onde:

 Q: finite set of states ∑: finite set of the input symbol q0: initial state F: final state δ: Transition function 

Modelo de autômatos finitos:

Autômatos finitos podem ser representados por fita de entrada e controle finito.

Fita de entrada: É uma fita linear com algum número de células. Cada símbolo de entrada é colocado em cada célula.

Controle finito: O controle finito decide o próximo estado ao receber uma entrada específica da fita de entrada. O leitor de fita lê as células uma por uma, da esquerda para a direita, e por vez apenas um símbolo de entrada é lido.

Tipos de autômatos:

Existem dois tipos de autômatos finitos:

1. DFA (autômatos finitos determinísticos)
2. NFA (autômatos finitos não determinísticos)

1. AFD

DFA refere-se a autômatos finitos determinísticos. Determinístico refere-se à singularidade da computação. No DFA, a máquina vai para um estado apenas para um determinado caractere de entrada. O DFA não aceita o movimento nulo.

2. NFA

NFA significa autômatos finitos não determinísticos. É usado para transmitir qualquer número de estados para uma entrada específica. Ele pode aceitar o movimento nulo.

Alguns pontos importantes sobre DFA e NFA:

1. Todo AFD é AFN, mas AFN não é AFD.
2. Pode haver vários estados finais tanto no NFA quanto no DFA.
3. DFA é usado em análise lexical no compilador.
4. NFA é mais um conceito teórico.