AUTOMATAS
FINITOS
CRISTIAN RAMIREZ
DIEGO PUSHAINA
CRISTIAN VARGAS
¿que son los
automatas finitos?
Los autómatas finitos también se denominan
máquinas de estados finitos. Son otra forma de
representar a los lenguajes regulares. La primera
forma ya tratada en este texto son las expresiones
regulares. En consecuencia, los autómatas finitos
también se usan para representar los tokens de un
lenguaje de programación.
AUTOMATAS FINITOS
Por lo tanto, es un modelo matemático de una máquina que
acepta cadenas de un lenguaje definido sobre un alfabeto A.
Consiste en un conjunto finito de estados y un conjunto de
transiciones entre esos estados, que dependen de los
símbolos de la cadena de entrada. El autómata finito acepta
una cadena x si la secuencia de transiciones
correspondientes a los símbolos de x conduce desde el
estado inicial a un estado final.
AUTOMATAS FINITOS
Si para todo estado del autómata existe como máximo
una transición definida para cada símbolo del alfabeto, se
dice que el autómata es determinístico (AFD). Si a partir
de algún estado y para el mismo símbolo de entrada, se
definen dos o más transiciones se dice que el autómata es
no determinístico (AFND).
¿que son los
automatas finitos?
En pocas palabras, los automatas finitos son
una forma de modelar en la que consideramos
a los objetos como máquinas que pueden pasar
por varios estados.
Componentes de un Autómata
Finito o defincion formal
Un automata finito se define formalmente como una 5-tupla (Q, Σ, δ, q0, F)
donde:
Estados (Q): Conjunto finito de estados en los que puede estar el autómata.
Alfabeto (Σ): Conjunto o alfabeto finito de símbolos de entrada.
Función de Transición (δ): Describe cómo cambia el estado del
autómata en respuesta a un símbolo de entrada.
Estado Inicial (q0): El estado en el que comienza el autómata.
Estados de Aceptación (F): Conjunto de estados finales en los que, si
termina la cadena de entrada, la cadena es aceptada.
Lenguaje Aceptado
por un Autómata
El lenguaje aceptado por un autómata finito es el conjunto de
todas las cadenas que, cuando se procesan desde el estado
inicial, terminan en uno de los estados de aceptación.
APLICACIONES DE AUTÓMATAS FINITOS
Compiladores: Utilizados en el análisis léxico para reconocer
tokens.
Procesamiento de Texto: Utilizados en herramientas de
búsqueda y reemplazo.
Controladores de Sistemas: Utilizados en sistemas embebidos
para modelar y controlar comportamientos de sistemas.
TABLA DE TRANSICION
Es una representación tabular de la función de transición de un autómata
finito, mostrando hacia qué estado se transita desde un estado dado para
cada símbolo del alfabeto.
DIAGRAMA DE TRANSICIÓN
Es una representación gráfica de un autómata finito donde los estados se
representan como círculos y las transiciones como flechas etiquetadas
con los símbolos de entrada.
EJEmplos
Podemos ver un semáforo como una máquina que puede pasar por los estados
rojo, verde y amarillo.
Podemos ver una silla como una máquina que pueden pasar por los estados
desocupada, ocupada, destruida.
Podemos ver a una persona como una máquina que puede pasar por los
estados soltero, casado, viudo, divorciado.
Un artículo en un almacén puede pasar por los estados: en exhibición,
separado, vendido, dado de baja.
La máquina en cuestión puede ser representada
gráficamente por un diagrama denominado
diagrama de transición, como el del siguiente
ejemplo.
EJEmplos
Cada nodo representa un estado: En
exhibición, Separado, Vendido, Dado de
baja.
Cada arista representa una transición,
lo que se necesita para el cambio de
estado.
En la figura, las transiciones son: Abono,
Vencimiento de plazo, Pago, Pago,
Devolución, Orden de dar de baja. El
estado En exhibición en este autómata
es el estado inicial. El estado inicial va
señalado con una flecha.
RESUMEN
Los autómatas finitos son un concepto
fundamental en la teoría de la computación y
las ciencias de la computación. El cual consiste
en un modelo matemático de una máquina de
estado finito que realiza cálculos sobre una
cadena de entrada y decide si la cadena
pertenece o no a un lenguaje específico.
MUCHAS
GRACIAS
