1 1. INTRODUCCIÓN:
Desde hace mucho tiempo, el deseo de obtener información o datos de forma exacta y correcta ha sido un gran problema en el campo de la matemática dado a que es un mundo complejo e infinito donde la perfección es el fin, sin embargo, con el tiempo se extendió a otros campos entre ellos el campo tecnológico, científico, entre otros; donde el organizar, calcular y usar de buena forma los datos se hacían de forma manual. En la actualidad, el uso de medios para establecer y realizar el procesamiento de información de manera mas eficiente, segura y exitosa ha ido creciendo a lo largo del tiempo, por lo que en consecuencia se han obtenido métodos excelentes de realizar este proceso utilizando el concepto de los autómatas que antes que un robot son dispositivos de permiten procesar la información antes mencionada causando una entrada y un resultado al final de dicho proceso.
El presente proyecto, permite conocer el funcionamiento de los dos tipos de autómatas que existen, los mismos que cumplen cada uno con varios requerimientos, varios pasos, y una forma diferente de resolverlos, sin embargo, teniendo resultados excelentes en el uso y tratamiento de datos, en este caso basándonos en lenguajes formales.
2 2. MARCO TEÓRICO:
AUTOMÁTAS FINITOS
Los Autómatas Finitos son maquinas teóricas que van cambiando de estado a medida que van recibiendo valores o cadenas en su entrada. Estos Autómatas se limitan a dos valores: aceptado y no aceptado, que pueden indicar si la cadena que se ha recibido como entrada es o no válida. Generalmente utilizaremos los Autómatas Finitos para reconocer lenguajes regulares, es decir, una palabra se consideraría válida sólo si pertenece a un determinado lenguaje.
Un autómata está representado gráficamente de la siguiente manera:
Óvalos: Los óvalos representan cada uno de los estados del autómata.
Flechas: Las flechas representan cada uno de los eventos o transiciones del autómata.
à: Es una marca que permita indicar donde se inicia el estado.
Óvalo Doble: Estado final. Una secuencia de eventos que llevó hasta ahí puede considerarse aceptable.
AUTÓMATAS FINITOS DETERMINISTAS.
Autómatas Finitos Deterministas o sus siglas AFD, son aquellos que poseen una estructura matemática definida y están formados de los siguientes elementos:
· S à Este símbolo representa un conjunto de estados.
· ∑ à Este símbolo representa un conjunto de símbolos o alfabeto.
· Una función move que mapea un par llamado P(s,a) de un estado S a un estado t, donde a es un símbolo y S y t son estados en S.
· S0 à Esto representa el estado inicial de una entrada o proceso.
· F à Este es el estado o conjunto de estados finales de un proceso.
Estos autómatas están formados por los siguientes componentes:
- · Cinta de entrada
- · Cabeza de lectura
- · Un control.
Los autómatas finitos deterministas se caracterizan además por tener dos premisas que debemos cumplir:
· NO existen transiciones etiquetadas con símbolo vacío.
· Por cada símbolo (a) y estado (S) existe un solo arco etiquetado por (a) y saliendo de (S).
¿Cómo resolver un AFD?
PASOS:
1. Definir las variables.
Letra M = [A - Z]
Letra m = [a - z]
2. Establecer el estado inicial, con una flecha y un nodo que se nombrara de forma secuencial.
3. Escribir la variable a usar en la transición.
4. Establecemos el nuevo estado en un nuevo nodo.
5. Verificamos si el estado es aceptable, es decir si podría terminar ahí nuestro autómata, esto dependerá de lo que se nos solicite validar; caso contrario volvemos al paso 3.
6. Verificamos si se requiere un nuevo estado, ya que en un autómata puede haber uno o varios estados de aceptación, si la respuesta es si volveremos al paso 3; caso contrario el ultimo nodo creado se establece como estado de aceptación final.
7. Es posible usar una transición recursiva en el mismo nodo de requerir que el dato que se encuentra ahí se repita n veces.
Ejemplo: Diseñar un AFD para validar el nombre de una persona (Mínimo 3 letras).
1 Proponer variables a usar:
· Letra M = [A - Z]
· Letra m = [a - z]
2 Diseñar AFD
1.1. Pasos de Diseño:
1.1.1. Identificar estados (condiciones que deben ser recordadas) y sus características.
1.1.2. Trazar las transiciones.
AUTÓMATAS FINITOS NO DETERMINISTAS.
Un autómata finito no determinista, o sus siglas AFND es un autómata finito que, a diferencia de los autómatas finitos deterministas (AFD), posee al menos un estado q ∈ Q, tal que para un símbolo a ∈ Σ del alfabeto, existe más de una transición δ(q,a) posible.
Los autómatas finitos no deterministas usan los mismos símbolos de lo autómatas finitos deterministas, sin embargo, cumplen con dos condiciones importantes, estas son:
· Posee transiciones etiquetadas con cadenas vacías.
· De un nodo salen 2 o más arcos etiquetados con el mismo símbolo.
Sin embargo, al realizar este tipo de autómata debemos tomar en cuenta ciertos problemas de desarrollo entre ellos:
· Dificultad para saber qué camino tomar
· Puede ser que no exista un camino con etiqueta a.
¿Cómo resolver un AFND?
PASOS:
1. Definir las variables.
pre1 = (http)
pre2 = (https)
puntos = (:)
slash = (/)
letras = [(a-z) (A-Z)]
num = [0-9]
dir = (www)
pun = (.)
2. Establecer el estado inicial, con una flecha y un nodo que se nombrara de forma secuencial.
3. Escribir la variable a usar en la transición.
4. Establecemos el nuevo estado en un nuevo nodo.
5. Verificamos si el estado es aceptable, es decir si podría terminar ahí nuestro autómata, esto dependerá de lo que se nos solicite validar; caso contrario volvemos al paso 3. En AFDN debemos analizar si es necesario que deba iniciar con otro estado, y se lo agregue.
6. Verificamos si se requiere un nuevo estado, ya que en un autómata puede haber uno o varios estados de aceptación, si la respuesta es si volveremos al paso 3; caso contrario el ultimo nodo creado se establece como estado de aceptación final.
7. Es posible usar una transición recursiva en el mismo nodo de requerir que el dato que se encuentra ahí se repita n veces.
Ejemplo: Diseñar un AFND para validar la URL de un sitio web.
1. Definir las variables a usar:
§ pre1 = (http)
§ pre2 = (https)
§ puntos = (:)
§ slash = (/)
§ letras = [(a-z) (A-Z)]
§ num = [0-9]
§ dir = (www)
§ pun = (.)
2. Diseñar el AFND
CONVERSIÓN DE AFND A AFD
La conversión de un AFND a un AFD es el procedimiento que se utiliza para transformar un autómata no determinista a un autómata finito determinista para su mejor comprensión y desarrollo en software. Para realizar una conversión de Autómata Finito no Determinista a un Autómata Finito Determinista, se pueden tomar en cuenta cuatro pasos:
1. Determinar e identificar los elementos del autómata que se presenta.
2. Agregar un estado de error al final, que contenga los símbolos del alfabeto.
3. Crear una tabla de transiciones, para obtener el AFD. Se debe iniciar del estado inicial de este estado veremos cuál es su siguiente estado con cero y luego con 1.
4. Una vez terminado el proceso de la tabla comenzamos la transformación y obtenemos el Autómata Finito Determinista.
¿Cómo transformar un AFND a un AFD?
Ejemplo:
1. Graficamos el Autómata Finito no Determinista.
2. Creamos la tabla de transición del autómata, identificando los estados y los símbolos manejados.
2.1. Colocamos de forma vertical cada uno de los estados.
2.2.Colocamos de forma horizontal cada uno de los símbolos usados en el autómata.
3. Realizamos el procedimiento de transformación, comparando cada uno de los estados según la transición:
3.1.Verificamos que desde el estado q0 sale el símbolo a hacia q1 y q2.
3.2.De igual manera se realiza la comparación con el siguiente símbolo.
3.3.Este proceso se realiza hasta terminar la comparación de todos los estados.
4. Graficamos el nuevo autómata finito determinista.
4.1. Tomamos cada uno de los estados y los graficamos en orden.
4.2.El estado inicial es q0 y la transición del símbolo a hacia q1 y q2 se grafica primero, luego se continua en orden.
JFLAP
Es un software educativo interactivo escrito en Java para experimentar con temas en el área de informática de lenguajes formales y teoría de autómatas, principalmente para uso a nivel de pregrado o como un tema avanzado para la escuela secundaria. JFLAP le permite a uno crear y simular estructuras, como programar una máquina de estados finitos, y experimentar con pruebas, como la conversión de un autómata finito no determinista (NFA) a un autómata finito determinista (DFA).[1]
Esta herramienta es de gran utilidad si de simular autómatas se trata y es sencillo obtenerla descargándola de internet. Tiene una interfaz muy amigable y simple de usar.
1. DESARROLLO:
1.1. Desarrollo del autómata finito no determinista.
1.2. Realización de la transformación de Autómata Finito no Determinista a Autómata Finito determinista.
1.3. Diseño del resultado del Autómata Finito Determinista.
2. CONCLUSIONES:
· El presente proyecto se ha realizado con éxito ya que se logro el desarrollo y comprobación de la transformación de un autómata finito no determinista a un autómata finito determinista.
· Mediante la investigación y el análisis además del uso de los conocimientos adquiridos en el aula logramos explicar los requerimientos y los pasos para obtener un resultado exitoso.
· Los resultados obtenidos son eficientes y comprobables mediante el uso de la herramienta JFLAP Simulator.
3. RECOMENDACIONES:
· Utilizar herramientas recomendadas y probadas a fin de no obtener errores en la resolución de los autómatas.
· En la grabación del video se sugiere usar un editor de buena calidad y preparar de antemano un guión a fin de no incurrir en errores durante su realización.
· La resolución de los ejercicios es mejor realizarla a mano a fin de no cometer errores y así usar la herramienta JFLAP como simulador y obtener autómatas sin errores.
4. BIBLIOGRAFÍA:
Brena, R. (2003). Automatas y Lenguajes.
Málaga, E. J. (2008). Teoria de Automatas y Lenguajes Formales. España: Universidad de Extremadura.
5. REFERENCIAS:
· http://virtual.ups.edu.ec/presencial51/pluginfile.php/305286/mod_resource/content/0/Capitulo1_3LenguajesRegularesAutomatasFinitos.pdf
Comentarios
Publicar un comentario