Matemática

Autómata finito



[pic]

Esquema lógico de un autómata finito.

[pic]

Un autómata finito o máquina de estado finito es un modelo matemático de un sistema que recibe una cadena constituida por símbolos de un alfabeto y determina si esa cadena pertenece al lenguaje que el autómata reconoce.

Los autómatas finitos son las herramientas empleadas como reconocedores de tokens.
Unautómata finito es capaz de reconocer un conjunto regular, es decir, un conjunto de cadenas denotado por cualquier expresión regular. Recordemos que una expresión regular denota a un lenguaje regular.
Un autómata finito es un reconocedor para un lenguaje, su programación no es una tarea
compleja, su entrada es una cadenax y responde“si” six es una sentencia del lenguaje,“no”
de otra manera


[pic][pic]Definición formal

Formalmente, un autómata finito (AF) puede ser descrito como una 5-tupla (S,Σ,T,s,A) donde:

• S un conjunto de estados;
• Σ es un alfabeto;
• T es la función de transición: [pic];
• [pic]es el estado inicial;
• [pic]es un conjunto de estados de aceptación o finales.

Definición de Configuración

Si A = [pic]es un AF, entonces (q,w) [pic]Qx [pic]es una configuración de A.
Configuración inicial: ([pic],w)
Configuración final : (q, [pic]),q [pic]F

Definición:

Si [pic](q,a)=q' entonces (q,aw) [pic](q',w) es un movimiento de A.
Un movimiento de A es representado por la relación binaria:
[pic]sobre configuraciones
[pic]+ movimiento transitivo de [pic]
[pic]hecho reflexivo transitivo de [pic]
Una cadena w [pic][pic]esaceptada por un AFND, A si ([pic],w) [pic](q,[pic]) para algún q [pic]F.
Un lenguaje aceptado por A es denotado por L(A) y es definido como:
L(A)={ w/w [pic][pic], ([pic],w) [pic](q,[pic]), q [pic]F }
Ejemplo 1
• S = {S1, S2},
• Σ = {0,1},
• T = {(S1,0,{S2});(S1,1,{S1});(S2,0,{S1});(S2,1,{S2})}
• s = S1
• A = {S1}.



Formas de representar un autómata finitoAdemás de notar un AF a través de su definición formal es posible representarlo a través de otras notaciones que resultan más cómodas. Entre estas notaciones, las más usuales son:

• Las Tablas de Transiciones: la tabla de transición para el AF del ejemplo 1 es

| |0 |1 |
|S1 |S2 |S1 |
|S2 |S1 |S2 |


• Los Diagramas de Transiciones: el diagrama de transición parael AF del ejemplo 1 es
[pic]
• Las Expresiones regulares. Se demuestra que dado un autómata de estados finitos, existe una expresión regular que lo representa. Ø υ 1* υ (1* ο 0 ο 1* ο 0)*



Descripción informal de su funcionamiento




En el comienzo del proceso de reconocimiento de una cadena, el AF se encuentra en el estado inicial y a medida que procesa cada símbolo de lacadena va cambiando de estado de acuerdo a lo determinado por la función de transición.

Cuando se ha procesado el último de los símbolos de la cadena de entrada, el autómata se detiene. Si el estado en el que se detuvo es un estado de aceptación o final, entonces la cadena pertenece al lenguaje reconocido por el autómata, caso contrario, la cadena no pertenece a dicho lenguaje.


[pic]
Ejemplo2:
Autómata finito determinístico que acepta el lenguaje

[pic]



Autómatas finitos deterministas




Un AFD o autómata finito determinista es aquel autómata finito cuyo estado de llegada está unívocamente determinado por el estado inicial y el carácter leído por el autómata.

Formalmente, un autómata finito determinista (AFD) es similar a un Autómata de estados finitos, representadocon una 5-tupla (S,Σ,T,s,A) donde:

• Σ es un alfabeto;
• S un conjunto de estados;
• T es la función de transición: [pic];
• [pic]es el estado inicial;
• [pic]es un conjunto de estados de aceptación o finales.


Al contrario de la definición de autómata finito, este es un caso particular donde no se permiten transiciones vacías, el dominio de la función T es S...