Edición de Autómatas Finitos No Determinísticos con Transiciones Vacías

Al ingresar desde el menú principal a Autómatas -> Finito -> No Determinístico con Transiciones Vacías (o utilizando la tecla rápida F4), se abre la ventana que permite la edición de autómatas finitos no determinísticos con transiciones vacías por medio de un grafo.


 

Esta ventana consiste en una barra de herramientas que incluye botones comunes a las diferentes ventanas de la aplicación y otros botones adicionales que permiten efectuar operaciones específicas de los autómatas finitos no determinísticos con transiciones vacías.

Por otro lado, se encuentra la definición formal del autómata que se está editando. El área de edición del grafo representa la función de transición de estados. A medida que se incorporan componentes en esta zona, la definición formal se va actualizando automáticamente, observándose el conjunto de estados, el alfabeto de símbolos de entrada, el estado inicial y el conjunto de estados finales. Estos componentes de la definición formal de un autómata finito no determinístico con transiciones vacías se observan en forma textual debajo del área de edición del grafo.

Barra de herramientas
En la parte superior de la ventana se encuentra una barra de herramientas que contiene 12 botones, 6 de los cuales corresponden a funciones comunes dentro de la aplicación mientras que los 6 restantes son específicos de esta ventana.

Editar nuevo autómata finito no determinístico con transiciones vacías
Presionando este botón se crea un nuevo autómata finito no determinístico con transiciones vacías en blanco.
Importante: Los cambios efectuados hasta el momento en el autómata que se estaba editando se perderán.

Abrir autómata finito no determinístico con transiciones vacías
Presionando este botón se puede abrir un autómata finito no determinístico con transiciones vacías guardado previamente en un archivo.
Importante: Los cambios efectuados hasta el momento en el autómata que se estaba editando se perderán.

Guardar autómata finito no determinístico con transiciones vacías
Presionando este botón se puede guardar el autómata finito no determinístico con transiciones vacías que se está editando en un archivo.

Imprimir autómata finito no determinístico con transiciones vacías
Presionando este botón se puede imprimir el autómata finito no determinístico con transiciones vacías que se está editando.

Ayuda sobre la edición de autómatas finitos no determinísticos con transiciones vacías
Presionando este botón se puede acceder a esta página de ayuda.

Salir
Presionando este botón se cierra la ventana.

Alfabeto de entrada
Presionando este botón se abre una ventana en la que se pueden ingresar los símbolos del alfabeto de entrada.

Reconocimiento de cadenas
Presionando este botón se abre una ventana en la que se puede ingresar una cadena a reconocer.

Incremento del área de edición del grafo
Presionando este botón se agranda el área de edición del grafo tanto a lo ancho como a lo alto.

Decremento del área de edición del grafo
Presionando este botón se achica el área de edición del grafo tanto a lo ancho como a lo alto.

Obtener autómata finito no determinístico equivalente
Presionando sobre este botón se abre una ventana en donde se muestra el autómata finito no determinístico resultante de aplicar el algoritmo de equivalencia entre AFND con transiciones vacías y AFND.

Obtener expresión regular equivalente
Presionando sobre este botón se abre una ventana en donde se muestra la expresión regular resultante de aplicar el algoritmo para obtener la expresión regular a partir de un AFND con transiciones vacías.
 

Edición del autómata finito no determinístico con transiciones vacías
En este área de la ventana se encuentran dos componentes diferentes. Uno de ellos es un panel en donde se edita la función de transición en forma interactiva y el otro es una barra de herramientas por medio de la cual se puede seleccionar el tipo de componente que se desea incorporar. Los botones correspondientes a dicha barra de herramientas son los siguientes:

Selección
Activando este botón se pueden seleccionar estados y transiciones. Una vez seleccionados los estados, pueden ser movidos dentro del panel de edición o eliminados. Las transiciones no se pueden mover libremente por el panel sino que son desplazadas cuando se mueve uno de los estados que vincula. Pero si una transición se encuentra seleccionada, la misma puede ser eliminada. Este botón permite también la edición del nombre de los estados y la incorporación de los símbolos de las transiciones.

Estado inicial
Luego de activar este botón se puede incorporar un estado inicial al autómata.

Estado inicial y final
Luego de activar este botón se puede incorporar un estado inicial y final al autómata.

Estado intermedio
Luego de activar este botón se puede incorporar un estado intermedio al autómata.

Estado final
Luego de activar este botón se puede incorporar un estado final al autómata.

Transición
Luego de activar este botón se puede incorporar una transición al autómata.
 

Incorporación de estados
Dependiendo del tipo de estado que se desee agregar, se presiona el botón correspondiente en la barra de herramientas de edición. Una vez seleccionado el tipo de estado correcto, se efectúa click sobre el panel de edición en el lugar en que se desea agregar el estado. Minerva le asigna automáticamente un nombre al nuevo estado, pero el mismo puede ser modificado luego.

Incorporación de transiciones
Para agregar una transición entre dos estados, se debe seleccionar el botón correspondiente a la incorporación de transiciones al autómata, luego presionar el botón del mouse sobre el estado que se desea que sea el origen y, sin soltar ese botón, desplazar el mouse hasta el estado destino y soltar el botón del mouse. En caso de tratarse de una transición sobre un mismo estado, el desplazamiento debe efectuarse sobre el estado del que se trata. Para asignar los símbolos que se encuentran asociados a las transiciones, primero se deben ingresar dichos símbolos al alfabeto de entrada.

Desplazamiento de estados dentro del área de edición
Para mover estados se debe optar por el botón de selección de componentes en la barra de herramientas de edición, luego presionar el botón del mouse sobre el estado que se desea mover y, sin soltar ese botón, desplazar el mouse hasta el lugar donde se desea ubicar el estado y soltar el botón del mouse. Al moverse un estado, todas las transiciones que se encuentran asociadas a él se desplazarán automáticamente.

Eliminación de estados y transiciones
Existen dos formas de eliminar estados y transiciones. Una es optando por el botón de selección de componentes en la barra de herramientas de edición, luego efectuar click sobre el estado o transición que se desea eliminar. De esta forma, el componente se marcará con color rojo. Una vez seleccionado el componente deseado, presionar la tecla DEL.
La otra forma provista para eliminar estados y transiciones es presionando el botón derecho del mouse sobre el componente que se desea eliminar. Con esta acción se desplegará un menú del cual se debe elegir la opción Eliminar.

Cambio de nombre de un estado
Para cambiar el nombre de un estado existente, se debe optar por el botón de selección de componentes en la barra de herramientas de edición y luego efectuar doble click sobre el estado cuyo nombre se desea modificar. Con esta acción, se puede ingresar el nuevo nombre del estado dentro del mismo gráfico que lo representa. Una vez completado el nombre, se debe presionar la tecla ENTER.

Incorporación y eliminación de símbolos de las transiciones
Antes de intentar incorporar símbolos a las transiciones, asegúrese de haber ingresado dichos símbolos al alfabeto de entrada.
Una vez efectuada esta operación, para agregar símbolos a las transiciones se debe optar por el botón de selección de componentes en la barra de herramientas de edición y efectuar doble click sobre la transición deseada. Con esta acción, se abre una ventana que permite la incorporación y eliminación de símbolos a la transición seleccionada.

Tipeando el símbolo deseado en el cuadro de texto se agregará el mismo a la transición. Si se desea asociar más de un símbolo a una transición, se debe presionar el botón  y se agrega un nuevo cuadro de texto en donde se puede incorporar el nuevo símbolo. En caso de desear eliminar un símbolo de la transición, se debe posicionar el cursor en el cuadro de texto correspondiente al mismo y presionar el botón  .
Para aceptar todos estos cambios se cebe presionar el botón Aceptar, en caso contrario se debe presionar el botón Cancelar.

Importante: El símbolo ' E ' está reservado como símbolo de la cadena vacía. Usted no debe agregarlo al alfabeto de entrada y puede utilizarlo como símbolo de cadena vacía para las transiciones.

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.

Incorporación de símbolos del alfabeto de entrada
Antes de agregar los símbolos correspondientes a las transiciones, se deben setear los símbolos que componen el alfabeto de símbolos de entrada del autómata finito no determinístico con transiciones vacías. Para llevar a cabo esta operación, se debe efectuar click sobre el botón  de la barra de herramientas tras lo cual se abre una ventana que permite el ingreso de los símbolos.

Para incorporar un nuevo símbolo solo debe tipearlo en el cuadro de texto y luego presionar el botón Agregar. Si desea eliminar un símbolo, debe marcarlo dentro de la lista efectuando click sobre el item correspondiente y luego presionar el botón Eliminar.
A medida que se agregan nuevos símbolos o se eliminan otros, la definición formal se actualiza en forma automática mostrando estos cambios. Una vez incorporados los símbolos deseados, se debe presionar el botón Cerrar que cierra la ventana de ingreso de símbolos al alfabeto de entrada y permite continuar con la edición del autómata finito no determinístico con transiciones vacías.

Importante: El símbolo ' E ' está reservado como símbolo de la cadena vacía. Usted no debe agregarlo al alfabeto de entrada y puede utilizarlo como símbolo de cadena vacía para las transiciones.

Reconocimiento de cadenas
Minerva permite verificar si el autómata finito no determinístico con transiciones vacías editado reconoce una cadena dada. Para ello se debe efectuar click sobre el botón  de la barra de herramientas con lo cual se abre una ventana que posibilita esta prueba.

En el cuadro de texto se debe tipear la cadena que se desea probar si es reconocida por el autómata finito no determinístico con transiciones vacías editado. Minerva provee dos formas de efectuar la comprobación del reconocimiento de la cadena ingresada. Se puede verificar en forma directa o bien por pasos, en cuyo caso, se van mostrando los símbolos reconocidos en cada paso y se van marcando los estados y transiciones por los cuales se pasa en el grafo editado.
Para efectuar la comprobación directa se debe efectuar click sobre el botón  que se encuentra en la barra de herramientas de la ventana de reconocimiento de cadenas. En la sección Resultado se muestra si el autómata finito no determinístico con transiciones vacías editado reconoce o no la cadena ingresada.
Para efectuar la comprobación por pasos se debe efectuar click sobre el botón  que se encuentra en la barra de herramientas de la ventana de reconocimiento de cadenas. Cada vez que se presiona ese botón, se ejecuta un paso en el reconocimiento de la cadena, se muestran los símbolos que han sido reconocidos hasta el momento y se marca en el editor de autómatas el estado y la transición correspondiente al paso actual. Una vez finalizados todos los pasos, en la sección Resultado se muestra si el autómata finito no determinístico con transiciones vacías editado reconoce o no la cadena ingresada. Durante el reconocimiento por pasos, se puede detener la operación utilizando el botón  , el efecto producido es la detención del reconocimiento por pasos y la próxima vez que se inicie la operación de reconocimiento, la misma se efectuará desde el inicio y no desde el paso en que se detuvo la operación anterior.

Importante: Si desea verificar si el autómata finito no determinístico con transiciones vacías editado reconoce la cadena vacía, debe dejar el cuadro de texto correspondiente al ingreso de la cadena a verificar en blanco. No debe tipear ' E ' para efectuar esta comprobación.


EjemploConceptos Teóricos