UNIVERSIDAD NACIONAL
"SANTIAGO ANTUNEZ DE MAYOLO"
FACULTAD DE CIENCIAS
ESCUELA PROFESIONAL DE INGENIERIA DE SISTEMAS
Departamento Académico : Ing. De Sistemas y Telecomunicaciones
Escuela Profesional : Ingeniería de Sistemas
Asignatura : Teoría de Lenguajes
Tema : Definición de autómatas, tipos, creación
de autómatas finitos determinista en el programa JFLAD
Semana nro. : 06
Huaraz, 15 de agosto del 2023
CAPACIDADES A LOGRAR
1.- Conocer y diferenciar el concepto de autómata.
2.- Conocer los tipos de autómatas.
3.- Conocer y representar un autómata finito determinista .
4.- Creación de autómata finito determinista n el programa JFLAD.
5.- Realizar ejemplos de creación de autómatas en el programa JFLAD.
Un autómata
Es una representación formal muy útil, que permite modelar el
comportamiento de diferentes dispositivos, máquinas, programas,
para ello pasan de un estado a otro.
Tipos de autómatas
1. El automata finite determinista(AFD)
Los AF son modelos matemáticos de un sistema que recibe entradas
(estímulos) discretas y proporciona salidas (acciones) discretas.
Un autómata finito va a permitir determinar en qué estado está un
determinado sistema entre un conjunto finito de estados.
Ejemplos.
Un interruptor, semáforos.
Un autómata no puede estas en mas de un estado al mismo tiempo
A un cambio de estado se denomina transiciones, las cuales suceden de
manera espontánea ó en respuesta a estímulos externos
El término “determinista” indica que para una entrada, existe un sólo
estado para el autómata.
La representación de un AFD consta de cinco componentes que
son los siguientes:
A= ( Q, ∑ , δ ,q0, F )
Donde:
Q: Un conjunto finito de estados
∑(sigma): Alfabeto de entrada (símbolos de entrada)
δ: Q X ∑ --> Q Función de transición, especifica a que estado pasa el autómata
Esta función se define para todas las posibles parejas de estados y
símbolos de entrada δ(q,a) = q’ significa que del estado “q” con el
símbolo “a”, el autómata pasa al estado q’
q0: Estado inicial.
F: Un conjunto de estados finales o de aceptación. F es un subconjunto de Q.
El proceso de reconocimiento es el siguiente:
El autómata comienza con el estado inicial cuando recibe el primer
símbolo y pasa al siguiente estado.
A partir del estado actual, se vuelve a procesar el siguiente símbolo
para pasar de forma iterativa a los siguientes estados
Al finalizar de procesar la cadena, si al llega a un estado final, la
cadena puede ser aceptada o rechazada.
Observaciones.
Un autómata finito determinista, tiene un conjuntos de estados
El autómata no puede estar en mas de un estado al mismo tiempo
Todo autómata tiene un estado inicial y final y se presentan gráficamente
de la siguiente manera
Estado inicial Estado final
Todo autómata puede pasar por diferentes estados, pero dentro de ese
conjunto de estados se encuentran el estado inicial como el estado final
La transición.
Permite el cambio de un estado a otro para el autómata, para ello necesita
Definir un conjunto de parejas entre el estado y el símbolo correspondiente,
la definición De parejas se realiza usando la función de transición.
Gráficamente se representa de la siguiente manera.
Símbolo
Transición
En esta figura se tiene un autómata que va a pasar por dos estados, un estado
inicial qo y un estado final q1
Mediante la transición se indica el cambio de estado para el autómata
A continuación vamos a crear un autómata finito determinista, con tres
estados, los cuales son: qo , q1 , q2
El autómata queda definido
de la siguiente forma
A= ( Q, ∑ , δ ,q0, F )
Donde se identifica:
Q: Los estados{q0,q1,q2}
∑={1,0} : El alfabeto
δ : La función de transición.
q0: El estado inicial
F: Un conjunto de estados finales
q2
Alfabeto
Vamos a crear la tabla de transición, para el autómata siguiente.
A={Q, ∑, δ , q0,F }
La tabla de transición es el siguiente.
Interpretación
Estando desde q0 recibimos 0 como entrada llegamos a q1 , para los demás se
sigue el mismo criterio para completar las celdas de la tabla.
Ingresando cadenas al autómata
A continuación vamos a ingresar las
cadenas para que el autómata verifique si
es valido o no valido. Para ello
seleccionamos la opción input/step by
State de la ventana del programa JFLAD ,
como resultado veremos la siguiente
ventana.
En la siguiente ventana ingresamos la cadena 10010 y damos click en el
botón aceptar.
Como resultado se muestra la siguiente ventana.
Se observa el primer estado
del autómata se encuentra con
un color de fondo oscuro, esto
indica que en este estado va
verificar si el primer valor (1)
de la cadena si es válida, para
ello damos click en el botón
step, el resultado se observara
en la siguiente ventana
Como se observa en la venta el 1
se encuentra de color gris, esto
indica que fue validado como
valido,
Pulsar click otra vez sobre el
botón step para validar el
siguiente valor (0) de la cadena,
como resultado también el 0 va
a cambiar color a gris pero se
cambió de estado a q1, es
decir que con el valor 0 el
autómata cambio del estado q0
al estado q1, con el valor 0,
también el autómata se
mantiene en el estado q1.
Seguidamente damos click sobre step, con el valor de 1 el autómata
paso al estado q2.
Finalmente damos clik sobre step
para coger el valor 0, con este
valor se mantiene en q2, porque
es el último estado, donde se
realiza la verificación final de la
cadena si es o no es válido, en
este caso el programa va asignar
un color de fondo verde donde se
encuentra las cadenas
ingresadas, eso significa que la
cadena ingresada es válida.
Existe otra forma de
ingresar las cadenas de
manera automática Para
ello seleccionar la
opción input/multiple
run, asi como se muestra
Como resultado se va mostrar la siguiente ventana donde se debe
ingresar la cadena y luego pulsar el botón Run Inputs de la venta que
se muestra para verificar si la cadena es validado por el autómata, es
decir si es o no es valida.
Después de haber dado click sobre el botón Run Inputs se muestra la
ventana donde se observa un mensaje indicando que la cadena es
aceptada.
Ejemplo de aplicaciones.
Considere un sistema formado por una lámpara y un interruptor. La
lámpara puede estar encendida o apagada. El sistema sólo puede recibir
un estímulo exterior: pulsar el interruptor. El funcionamiento es habitual: si
se pulsa el interruptor y estaba apagada la lámpara, se pasa al estado de
encendido, o si esta encendida, pasa a pagada. Se desea que la lámpara
este inicialmente apagada, Considere que 0: encendido, 1: apagado y la
única entrada posible (pulsar interruptor) es “p”
¿Cómo sería el autómata que representa a este sistema?
Solución
Definimos el autómata
A={Q, ∑, δ , q0,F }
Identificamos los elementos para el autómata
1.- Definimos el conjunto de estados Q={q0, q1, q2}
2.- Definimos el alfabeto: ∑={0,1)
3.- Definimos la función de transición : δ: Q X ∑ --> Q
Definimos las todas las parejas posibles de estados y símbolos para cada
estado del autómata
( q0,1)= q0; del el estado q0, y símbolo 1 el estado será q0,
q0,0)= q1 ; del estado q0 y el símbolo 0 el estado será q 1
(
( q1,0)= q1
( q1,1)= q2
(q2,0) = q2
( q2,1)= q2
4.- Definimos el estado inicial : q0
5.- El conjunto de estados de aceptación será: F={ q2}
6.- Ingresamos la cadena para validar por el autómata:
w={100101}
Después de haber ingresado la cadena al autómata, se observa
que fue reconocido como por lo tanto la cadena es valida,
porque se aprecia un resultado de Accept
