Ejemplo de Autómata Finito No Determinístico con Transiciones Vacías

Se va a mostrar el uso de Minerva en autómatas finitos no determinísticos con transiciones vacías mediante el desarrollo de un ejemplo.
El lenguaje con que se va a trabajar es L = { x / x Î {0, 1}* y x contiene la subcadena 00 ó x contiene la subcadena 11}

A continuación se describen los pasos a seguir para editar el autómata finito no determinístico con transiciones vacías anteriormente descripto utilizando Minerva.

Edición de un autómata finito no determinístico con transiciones vacías
Primero, se debe acceder a la ventana de edición de atuómatas finitos no determinísticos con transiciones vacías desde el menú principal por medio de las opciones las opciones Autómatas -> Finito -> No Determinístico con Transiciones Vacías(o utilizando la tecla rápida F4). De esta forma, se muestra un diálogo con las opciones Abrir y Nuevo, optar por esta última opción.

Con esta acción se muestra un diálogo en donde se debe ingresar el nombre del archivo en donde se desea guardar el autómata finito no determinístico con transiciones vacías a editar.

Luego de haber ingresado el nombre del archivo, se debe presionar sobre el botón Aceptar, lo cual conduce a que se abra la ventana en donde se puede comenzar con la edición del autómata finito no determinístico con transiciones vacías.


 

Ingreso de los estados
Los estados que forman parte del autómata se crean seleccionando el tipo adecuado en la barra de herramientas que se encuentra en el área de edición y efectuando click sobre el panel de edición. Note que a medida que ingresa nuevos estados, la definición formal se actualiza en automáticamente.
Agregue el estado inicial del autómata, aunque debe tener en cuenta que el orden en que se agreguen los estados es arbitrario. Para agregar, entonces, el estado inicial, seleccione el segundo botón de la barra de herramientas y presione el botón izquierdo del mouse sobre el panel de edicón.

Para ingresar, ahora, los estados intermedios, debe seleccionar el cuarto botón de la barra de herramientas y, nuevamente, efectuar click sobre el panel de edición.

Por último queda agregar los estados finales, presionando el quinto botón de la barra de herramientas y haciendo click sobre el panel de edición se obtiene el siguiente resultado.


 

Ingreso de los símbolos del alfabeto de entrada
Antes de asociar los símbolos correspondientes a las transiciones, los mismos deben ser ingresados al alfabeto de entrada. Sin embargo, las transiciones (sin sus símbolos) pueden ser ingresadas previamente. Note que a medida que ingresa nuevos símbolos al alfabeto de entrada, la definición formal se actualiza automáticamente.
Pero ahora, defina el alfabeto de entrada seleccionando la opción  de la barra de herramientas que se encuentra en la parte superior de la ventana. Con esta acción se abrirá una ventana en la que podrá incorporar los símbolos.

Para ingresar cada uno de los símbolos, tipeelos en el cuadro de texto correspondiente y presione la tecla ENTER o bien el botón Agregar. Si fuese necesario eliminar alguno de los símbolos ingresados, selecciónelo en la lista con el botón izquierdo del mouse y presione el botón Eliminar. Una vez definido el alfabeto de entrada completo, presione el botón Cerrar.
 

Ingreso de las transiciones
Para ingresar las transiciones que conforman el autómata finito no determinístico con transiciones vacías, debe seleccionar el sexto botón de la barra de herramientas de edición. Luego, presione el botón izquierdo del mouse sobre el estado que desea considerar como origen, sin liberar este botón, desplace el mouse hacia el estado destino y libere el botón del mouse sobre este último estado. De esta forma debe crear todas las transiciones necesarias.


 

Asociación de los símbolos a las transiciones
Recuerde que los símbolos que quiera asociar deben formar parte del alfabeto de entrada. Para agregar estos símbolos a las transiciones, efectúe doble click sobre la transición deseada y se abrirá un diálogo en donde puede tipear un símbolo. Para incorporar otro, presione el botón  , si fuese necesario eliminar algún símbolo ingresado, efectúe click sobre dicho símbolo y presione el botón  . Recuerde que el símbolo ' E ' pertenece a la cadena vacía, por lo tanto, en caso de desear incorporar una transición vacías tipee el símbolo 'E' en el cuadro de texto correspondiente al símbolo asociado a la transición.

Una vez incorporados los símbolos deseados, presione el botón Aceptar.
Luego de haber efectuado esta operación para cada una de las transiciones que forman parte del autómata finito no determinístico con transiciones vacías que se está tratando como ejemplo, el resultado será el siguiente.

Nota: Si la transición a la que desea asociarle símbolos se encuentra debajo de otra, presione el botón derecho del mouse sobre la que está arriba y en el menú emergente seleccione la opción Enviar al fondo, de esta forma, la próxima vez que efectúe click en ese lugar, la transición accesible será la que anteriormente se encontraba debajo.

Operaciones sobre el autómata finito no determinístico con transiciones vacías editado

Reconocimiento de cadenas
Una de las operaciones que se pueden llevar a cabo es la verificación de si el autómata reconoce las cadenas dadas. Para llevar a cabo esta operación debe presionar el botón  de la barra de herramientas, con lo cual se abre un diálogo que permite efectuar esta comprobación. Ingrese la cadena deseada en el campo de texto correspondiente. Si, por ejemplo, ingresa la cadena 001010 se puede comprobar que el autómata finito no deteminístico con transiciones vacías editado la reconoce. Existen dos formas de comprobarlo, la primera corresponde al reconocimiento directo y la segunda al reconocimiento por pasos.

Reconocimiento directo
Para comprobar si el autómata finito no determinístico con transiciones vacías editado reconoce una cadena dada en forma directa, luego de ingresar la cadena en el campo de texto, presione el botón  que se encuentra en la barra de herramientas del diálogo Reconocimiento de Cadenas. El resultado de esta comprobación se mostrará en la sección Resultado de este diálogo.

En caso de no ser reconocida, en la sección Resultado del diálogo Reconocimiento de Cadenas se muestra este resultado. Por ejemplo, al ingresar la cadena 01010 se puede observar que el autómata finito no determinístico con transiciones vacías editado no la reconoce.


 

Reconocimiento por pasos
Para comprobar si el autómata finito no determinístico con transiciones vacías editado reconoce una cadena dada observando su comportamiento paso a paso, luego de ingresar la cadena en el campo de texto, presione el botón  que se encuentra en la barra de herramientas del diálogo Reconocimiento de Cadenas. Cada vez que se presione este botón, se irán mostrando los símbolos reconocidos hasta el momento y se marcarán con color rojo el estado y la transición actuales en el grafo editado.

Una vez finalizada la comprobación se muestra el resultado en la sección Resultado de este diálogo de la misma forma que para el reconocimiento directo.
Si deseara cortar el reconocimiento por pasos, por ejemplo para modificar la cadena de entrada, presione el botón  . Si realiza esta operación, la próxima vez que inicie el reconocimiento, el mismo se efectuará desde el comienzo.
 

Obtención del autómata finito no determinístico equivalente
Otra operación que se puede efectuar sobre el autómata finito no determinístico con transiciones vacías editado es la obtención del autómata finito no determinístico equivalente. Para ello, solo debe presionar el botón  que se encuentra en la barra de herramientas. Con esto, se abrirá una nueva ventana de edición de autómatas finitos no determinísticos que contiene el autómata buscado. Para el ejemplo dado, se puede observar que el resultado es el siguiente.

Si desea, puede obtener el auómata finito determinístico equivalente al AFND obtenido presionando el botón  correspondiente a esta útlima ventana abierta. El resultado de efectuar esta operación es el siguiente.

Ahora, a partir del AFD obtenido puede obtener el auómata finito determinístico con cantidad mínima de estados equivalente presionando el botón 
correspondiente a esta útlima ventana abierta. El resultado de efectuar esta operación es el siguiente.


 

Obtención de la expresión regular a partir del autómata finito no determinístico con transiciones vacías editado
Con el uso de Minerva se puede obtener la expresión regular a partir del autómata finito no determinístico con transiciones vacías editado presionando el botón  que se encuentra en la barra de herramientas. Con esto, se abrirá una nueva ventana de edición de expresiones regulares que muestra la correspondiente al autómata finito no determinístico con transiciones vacías editado. Para el ejemplo dado, el resultado es el siguiente.

Si eliminamos los paréntesis redundantes, resulta la expresión regular (0+1)*00(0+1)*+(0+1)*11(0+1)* que describe el lenguaje dado como ejemplo.


Conceptos Teóricos