Autômatos finitos

 

Reconhecedor Determinístico Finito (RDF)

São reconhecedores de linguagens regulares definidos através de quíntuplas da forma:

M=(Q,\ \Sigma,\ \delta,\ q_{0},\ F)
  • \, Q é um conjunto finito não vazio de estados do autômato;
  • \,\Sigma é um conjunto de símbolos, denominado alfabeto de entrada do autômato;
  • \,\delta:Q \times \Sigma \to Q é a função de transição de estados do autômato e seu papel é o de indicar as transições possíveis em cada configuração do autômato. Esta função fornece para cada par "estado e símbolo de entrada" um novo estado para onde o autômato deverá mover-se.
  • \,q_{0}\in\, Q é denominado estado inicial do autômato finito. É o estado para o qual o reconhecedor deve ser levado antes de iniciar suas atividades.
  • F\subseteq Q é um subconjunto do conjunto Q dos estados do autômato, e contém todos os estados de aceitação ou estados finais do autômato finito. Estes estados são aqueles em que o autômato deve terminar o reconhecimento das cadeias de entrada que pertencem à linguagem que o autômato define. Nenhuma outra cadeia deve ser capaz de levar o autômato a qualquer destes estados.