El autómata finito es una máquina que se utiliza para reconocer patrones. FA acepta o rechaza una entrada basada en un conjunto de cadenas ya definido conocido como el lenguaje del autómata.
Un autómata/máquina finito tiene un número finito de estados donde un estado puede ser un estado de aceptación o un estado de rechazo. Toma una secuencia de entrada y cambia su puntero de estado actual de acuerdo con las reglas de la máquina conocidas como función de estado. Una vez que finaliza la secuencia de entrada, el estado actual de la máquina determina si la entrada se acepta o rechaza según el tipo de estado. En otras palabras, si el estado actual/activo de una máquina después de que finaliza la entrada dada, es un estado de aceptación, se sabe que la entrada es aceptada y viceversa.
Por lo tanto, un autómata finito está diseñado para dar como resultado un estado de aceptación si la entrada se encuentra en el idioma (conjunto de cadenas) que queremos reconocer. También viceversa.
Un ejemplo sencillo de fa es el del control de seguridad de los aviones. Realiza un seguimiento del estado del avión, como combustible, puertas abiertas, aletas en funcionamiento, etc. Diferentes eventos cambian el estado del control de seguridad del avión, lo que puede resultar en un estado de aceptación (que permite arrancar el motor y despegue) o un estado de rechazo. si el avión no está en condiciones de realizar un vuelo seguro.
Representación metamática
Un autómata finito se representa matemáticamente por
$$ (\text{Q} \text{,} Σ \text{,} δ \text{,} \text{q} \text{0} \text{,} \text{F} ) $$
Donde,
Q: conjunto de todos los estados.
Σ(Alfabeto): todos los símbolos posibles para una entrada.
δ (Función de transición): las reglas que especifican el siguiente estado.
q 0 : el estado inicial
F: conjunto de estados de aceptación
Ejemplo
Vamos a crear FA que acepte cadenas que comiencen con ‘aa’
Aquí,
Q: {a1,a2,bien,nunca}
Σ(Alfabeto): {a,b,c, ….} (finito)
q 0 : ‘todavía no hay entrada’
F: {bien}
δ (Función de transición ):
| Expresar | Para ingresar un | para cualquier otra cosa |
|---|---|---|
| a1 | a2 | nunca |
| a2 | de acuerdo | nunca |
| nunca | nunca | nunca |
| de acuerdo | de acuerdo | de acuerdo |
Diseño y Símbolos
El autómata finito también se puede representar gráficamente para comprender fácilmente lo que está sucediendo. Tratar de comprender el lenguaje de una máquina a través de su función de transición de estado es muy difícil. La función de transición de estado es buena para las computadoras, mientras que los humanos encuentran más cómodo el diagrama de estado.
Estados que no aceptan/rechazan
Los estados de no aceptación son los estados en los que si la cadena de entrada finaliza, la entrada se considera rechazada.
Estados de aceptación
Los estados de aceptación son los estados en los que si la cadena de entrada finaliza, la entrada se considera aceptada.
Estados trampa
Para algunos idiomas, una máquina puede determinar si una cadena es válida o no en una etapa temprana y después de lo cual ningún símbolo tiene ningún efecto en el resultado, dicho estado se conoce como estado trampa.
Transición de estado
donde el símbolo de transición es el carácter en la entrada que da como resultado la transición.
Tipos
Los diferentes tipos de autómatas finitos son
- Autómatas finitos deterministas
- Autómatas finitos no deterministas
Vamos a discutir los ejemplos allí.