AUTOMATAS FINITOS

AUTOMATAS FINITOS
Un autómata finito es una estructura matemática que representa un sistema o maquina abstracta.
Los autómatas finitos pueden considerarse como mecanismos aceptadores o reconocedores de palabras. De manera informal decimos que un autómata finito aceptará una palabra de entrada si, comenzando por un estado especial llamado estado inicial y estando la cabeza de lectura apuntandoal primer símbolo de la cadena, la maquina alcanza un estado final o de aceptación después de leer el ultimo símbolo de la cadena.
Los AF constan de cinco elementos fundamentales AF= (∑, E, F, s, ᵹ). Un alfabeto (∑), un conjunto de estados (E), un estado inicial (s), un conjunto de estados finales (F) y una función ᵹ: E x ∑ → E que permite determinar cuál es el estado siguiente.
Lasrepresentaciones regulares de pueden representar por medio de autómatas finitos, a su vez los autómatas finitos pueden expresarse en forma gráfica por medio de un diagrama de transición o bien por medio de una tabla que recibe el nombre de tabla de transición.
Diagrama de transición
En los diagramas de transición, los estados se representan por medio de un círculo con el nombre del estado dentro de él. Losestados de aceptación o finales se distinguen porque tienen doble círculo, las transiciones se representan por aristas y se etiquetan con un símbolo del alfabeto. El estado inicial se distingue porque se hace incidir sobre él una flecha. Por ejemplo, el diagrama de transición que permite representar a la expresión regular (0 ᴜ 1) *01 es el siguiente:
1 0
0

10 1

Aquí se tiene que:
∑= (0,1) es el alfabeto.
E= (q0, q1, q2) es el conjunto de estados.
S= q0 es el estado inicial, que se reconoce por la flecha que incide en él.
F= {q2} conjunto de estados finales, que se distinguen por el doble círculo.
ᵹ: E x ∑ → E es la función para determinar el estado siguiente.
En el diagrama de transición se puede observar que pertenecen al lenguajeindicado por la expresión regular (0 ᴜ 1) *01 cadenas de caracteres que terminan con 01. Por ejemplo, las cadenas 10001 y 101 pertenecen al lenguaje.
La función de transición ᵹ: E x ∑ → E permite determinar el estado siguiente, partiendo el par estado (E) y un símbolo del alfabeto (∑) para acceder a otro estado del conjunto E.
Por ejemplo, si la cadena es 10001, la ruta que se sigue para reconocer lacadena es:
ᵹ(q0,1) = q0 se inicia en el estado inicial q0 y con el símbolo 1, nuevamente el estado siguiente es q0 como se puede ver en el diagrama de transición.
ᵹ(q0,0) = q1 De q0 y con el símbolo 0 se traslada a estado q1.
ᵹ(q1,0) = q1 De q1 y con el símbolo 0 permanece en q1.
ᵹ(q1,0) = q1 De q1 y con el símbolo 0 permanece en q1.
ᵹ(q1,1) = q2 De q1 y con el símbolo 1 se traslada a q2.
Como q2es un estado de aceptación, se dice que la cadena 10001 pertenece al lenguaje.
Algunas veces es más fácil indicar la ruta que se sigue para evaluar la cadena de la siguiente manera:
1
0
0
0
1

q0

q0

q1

q1

q1

q2

De esta misma forma la cadena 1011010 no pertenece al lenguaje, como se muestra a continuación:
1
0
1
1
01
0

q0

q0

q1

q2

q0

q1

q2

q1

Ya que el estado q1 donde queda finalmente, no es un estado de aceptación.





APLICACIÓN DE AUTÓMATAS
En la actualidad los autómatas están definitivamente en todo diseño que permite el funcionamiento de dispositivos, tales como robots, calculadoras, fotocopiadoras, computadores, controladores, etc.
Ahora haremos un análisis acerca del funcionamiento de undispositivo de impresión, para el diseño de este autómata tuvimos que abstraernos para obtener los posibles estados con sus respectivas condiciones que permite la impresión de archivos.

AUTÓMATA DE IMPRESIONES.
Estados del dispositivo:
APA: Dispositivo apagado.
REP: Dispositivo en reposo.
ENC: Dispositivo encendido.
RPE: Revisando archivos en el puerto de entrada.
RME: Revisando archivos en la...