Automátas Finitos Deterministas y no Deterministas

Los autómatas finitos son máquinas de estados que nos pueden ayudar a reconocer palabras que sean válidas en un lenguaje regular. Su funcionamiento básico es realizar transiciones de acuerdo a una función de transición que indica hacia dónde se mueve el autómata. 

A partir del estado inicial mediante símbolos de entrada el autómata realiza transiciones para poder aceptar o no un conjunto de caracteres. El autómata está definido de la siguiente manera   A = (Q, Σ, ∂, S1, F) donde: 

• Q: conjunto de todos los estados del automáta. 
• Σ: alfabeto del lenguaje regular, conjunto de todos los símbolos que pertenecen a este. 
• ∂: función de transición, nos indica las transiciones que realiza el autómata dado el símbolo que se esté analizando. 
• S1: estado inicial. No necesariamente debe utilizarse "S1", puede utilizarse el nombre que se desee. 
• F: conjunto de estados de aceptación o estados finales. Si al finalizar las transiciones el autómata termina en uno de estos estados entonces se acepta la cadena. 

El objetivo del autómata finito en general es reconocer si una palabra es válida o no para un lenguaje regular. 

Autómatas finitos deterministas (AFD)

Los autómatas finitos deterministas tienen la característica de que para una entrada solo hay un posible movimiento a otro estado, es decir no hay dos posibilidades de transición con el mismo símbolo para un estado. Por ejemplo:

Automatas finitos no deterministas (AFND)

A los autómatas que tienen ambigüedad o que pueden realizar un transicion a dos estados distintos con el mismo símbolo le llama autómata finito no determinista

Ejemplo: 

Tomando una expresión regular  ( 0 | ( 0* 1)* ) 1 la cual está representada por el siguiente autómata:

1. Q = { A, B, C, D, E } 

2. A

3. Σ = { 0, 1}

4. F = { C }

5. Función de transición

 

∂(A, 0 ) = B		∂(A, 1 ) = C
∂(B, 0 ) = D		∂(B, 1 ) = C
∂(C, 0 ) = D		∂(C, 1 ) = C
∂(D, 0 ) = D		∂(D, 1 ) = E
∂(E, 0 ) = D		∂(E, 1 ) = C

 

Diagrama del autómata finito determinista

Para generar los autómatas a partir de expresiones regulares se puede utilizar el método del árbol y el de Thomson.