Autómata finito

Un autómata finito ou máquina de estados finita é un modelo matemático que representa unha linguaxe.

Conceptos

Introduciranse a continuación unha serie de conceptos para definir formalmente un autómata finito:

• Chámase alfabeto, e denotarase A, a un conxunto de símbolos.
• Chámase palabra a unha sucesión de símbolos, xeralmente dun alfabeto dado.
• Chámase linguaxe a un conxunto de palabras formadas por símbolos dun alfabeto dado.

Cada autómata finito representa unha linguaxe e é quen de recoñecer as palabras desta. Así mesmo, pódese usar un autómata finito para xerar palabras dunha linguaxe. Tanto para recoñecer palabras como para xeralas os autómatas sérvense dun conxunto de estados e dunha función de transición que permite moverse dun estado a outro en función do símbolo do alfabeto que se recibe.

A seguinte figura mostra un exemplo:

Definición formal

Defínese formalmente un autómata finito mediante unha 5-tupla

$M=(S,A,T,s,F)$, onde:

• S é un conxunto de estados.
• A é un alfabeto.
• T é unha función de transición, definida como $T:SxA->S$.
• s elementoDe S é o estado inicial.
• F subconxuntoDe S é o conxunto de estados de aceptación ou finais.

Defínese a linguaxe que recoñece un autómata finito como:

$L(M)={xelementoDeA*|T(s,x)elementoDeF}$

Exemplo

Un exemplo de autómata finito sería:

M = (S, A, T, q0, F), onde

S = {q0, q1, q2}

A = {a, b}

T vén dada por:

T (q0, a) = q1, T (q0, b) = q2

T (q1, a) = q1, T (q1, b) = q2

T (q2, a) = q1, T (q2, b) = q0

s = q0

F = {q1}

O autómata finito do exemplo recoñece cadeas rematadas en b.

Os autómatas finitos poden ser representados, ademais de pola súa definición formal, mediante unha táboa de transicións, mediante un diagrama de transicións ou mediante un grafo. Neste último caso os estados corresponderanse cos nodos do grafo e a función de transición representaríase mediante os enlaces, sendo a etiqueta do enlace o símbolo que recibe a función de transición.

Os autómatas finitos poden ser deterministas ou non deterministas.