- 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:
- DFA (autômatos finitos determinísticos)
- 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:
- Todo AFD é AFN, mas AFN não é AFD.
- Pode haver vários estados finais tanto no NFA quanto no DFA.
- DFA é usado em análise lexical no compilador.
- NFA é mais um conceito teórico.