Edición de Máquinas de Turing No Determinísticas


Al ingresar desde el menú principal a Autómatas -> Máquina de Turing -> No Determinística (o utilizando la tecla rápida F12), se abre la ventana que permite la edición de máquinas de Turing no determinísticas por medio de una tabla.

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 las máquinas de Turing no determinísticas.

Por otro lado, se encuentra la definición formal de la máquina de Turing que se está editando. El área de edición de la tabla representa la función de transición de estados. En el momento de efectuar una operación con la máquina de Turing no determinística editada se actualiza la definición formal, observándose el conjunto de estados, el alfabeto de símbolos de entrada, el estado inicial, el conjunto de estados finales, el alfabeto de símbolos de las cintas y el símbolo que representa el blanco. Estos componentes de la definición formal de una máquina de Turing no determinística se observan en forma textual debajo del área de edición de la tabla.
 

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

Editar nueva máquina de Turing no determinística
Presionando este botón se crea una nueva máquina de Turing no determinística en blanco.
Importante: Los cambios efectuados hasta el momento en la máquina de Turing que se estaba editando se perderán.

Abrir máquina de Turing no determinística
Presionando este botón se puede abrir una máquina de Turing no determinística guardada previamente en un archivo.
Importante: Los cambios efectuados hasta el momento en la máquina de Turing que se estaba editando se perderán.

Guardar máquina de Turing no determinística
Presionando este botón se puede guardar la máquina de Turing no determinística que se está editando en un archivo.

Imprimir máquina de Turing no determinística
Presionando este botón se puede imprimir la máquina de Turing no determinística que se está editando.

Ayuda sobre la edición de máquinas de Turing no determinísticas
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 y símbolos auxiliares
Presionando este botón se abre una ventana en la que se pueden ingresar los símbolos del alfabeto de entrada y los auxiliares.

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

Definir estados
Presionando sobre este botón se abre una ventana en la que se pueden definir el estado inicial y los estados finales de la máquina de Turing no determinística.
 

Edición de la máquina de Turing no determinística
En este área de la ventana se encuentran dos componentes diferentes. Uno de ellos es una tabla en donde se edita la función de transición y el otro es una barra de herramientas por medio de la cual se pueden agregar y eliminar cintas. Los botones correspondientes a dicha barra de herramientas son los siguientes:

Incoporación de una cinta
Presionando este botón se agrega una cinta a la máquina de Turing no determinística.

Eliminación de una cinta
Presionando este botón se abre un diálogo que permite eliminar una de las cintas de la máquina de Turing no determinística.
 

Definición de la función de transición
Para definir la función de transición, se deben tipear los estados, símbolos y movimientos correpsondientes dentro de la tabla. Para ingresar tanto los símbolos como los estados, debe efectuar click sobre la casilla de la tabla que desee y tipear el símbolo o estado correspondiente. Para ingresar el movimiento, presione click sobre la celda de movimiento deseada y se desplegará una lista con los posibles movimientos a ingresar. Para desplazarse por la tabla puede efectuarlo con las flechas del teclado o bien con la tecla ENTER. Una vez que se desplace a una casilla donde se pueda incoporar un símbolo o un estado, puede tipearlo directamente, sin necesidad de presionar click sobre dicha celda. Sin embargo, esto no ocurre con los movimientos para los cuales obligatoriamente deberá efectuar click sobre la casilla.

Incorporación y eliminación de filas
En caso de desear incorporar una fila al final de la tabla debe posicionarse en la celda correspondiente a la última fila y última columna de la tabla y presionar ENTER. Si, en cambio, se desea agregar una fila en el medio, debe posicionarse en la fila que desea desplazar hacia abajo y presionar el botón derecho del mouse, esta acción abrirá un menú en el cual deberá elegir la opción Insertar Fila.
Para eliminar una fila, posiciónese en la fila que desea eliminar y presione el botón derecho del mouse, luego, del menú emergente, seleccione la opción Eliminar Fila.

Incorporación de una cinta
Para agregar una cinta a la máquina de Turing, presione el botón  que se encuentra en la barra de herramientas de edición. Automáticamente se agregará una cinta a la máquina de Turing no determinística que está editando.

Eliminación de una cinta
Para eliminar una cinta a la máquina de Turing, presione el botón  que se encuentra en la barra de herramientas de edición y se abrirá un diálogo en donde puede colocar el número de cinta que desea eliminar.

Una vez ingresado el número de cinta a eliminar, presione el botón Aceptar y la cinta será eliminada en forma automática.

Definición del estado inicial y los estados finales
Antes de poder efectuar alguna de las operaciones que se pueden llevar a cabo por medio de Minerva con la máquina de Turing no determinística editada, se debe definir cuál es el estado inicial y cuáles son los estados finales, además de los símbolos del alfabeto de entrada y los auxiliares.
Para definir los estados, debe presionar el botón  con lo cual se abre un diálogo en donde se pueden setear estos estados.

El nombre del estado inicial debe ser ingresado en el cuadro de texto etiquetado como Estado Inicial y los estados finales se incorporan tipeando el nombre de cada uno de ellos en el cuadro de texto que se encuentra en el área titulada Estado Final y presionando el botón Agregar. Una vez definidos el estado inicial y todos los estados finales, presione el botón Cerrar. Note que al cerrar este diálogo la definición formal de la máquina de Turing se actualiza en forma automática incorporando estos cambios con respecto a los estados.

Incorporación de símbolos del alfabeto de entrada y los auxiliares
Antes de poder efectuar alguna de las operaciones que se pueden llevar a cabo por medio de Minerva con la máquina de Turing no determinística editada, se deben setear los símbolos que componen el alfabeto de símbolos de entrada y los auxiliares, además de definir cuál es el estado inicial y cuáles son los estados finales. Para incoporar los símbolos a los alfabetos correspondientes 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 dichos símbolos.

Para incorporar un nuevo símbolo solo debe tipearlo en el cuadro de texto correspondiente, según al alfabeto que desee agregarlo, 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 los símbolos auxiliares y permite continuar con la edición de la máquina de Turing no determinística.

Reconocimiento de cadenas
Minerva permite verificar si la máquina de Turing editada reconoce una cadena dada. Es importante que antes de intentar llevar a cabo esta operación, se asegure de haber definido los estados y los símbolos del alfabeto de entrada y los auxiliares. Para comenzar con la comprobación de si la máquina de Turing reconoce una cadena, se debe efectuar click sobre el botón  de la barra de herramientas con lo cual se abre una ventana que posibilita esta prueba.

Además, se abre una ventana en donde se muestra el estado de las cintas que forman la máquina de Turing editada. En los casilleros de las cintas se van actualizando en forma automática los símbolos escritos y se muestra con fondo rojo y letras blancas el casillero en donde se encuentra posicionada la cabeza lectora.

Para poder comprobar si la máquina de Turing reconoce una cadena dada, la misma debe ser tipeada en el cuadro de texto ubicado en el diálogo titulado Reconocimiento de Cadenas. 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 va mostrando la configuración de las cintas en cada uno de los pasos ejecutados.
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 la máquina de Turing no determinística editada reconoce o no la cadena ingresada y en la ventana de las cintas se muestra la configuración final de la máquina de Turing.
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 y se muestra la configuración actual de la máquina de Turing en la ventana correspondiente al estado de las cintas. Además, se muestra con color rojo la fila de la tabla correspondiente a la transición por medio de la cual se llegó al estado actual con la configuración mostrada en el ventana de cintas. Con color azul se muestra la fila que representa la transición a partir de la cual se debe buscar un camino diferente para efectuar el reconocimiento debido al no determinismo de la máquina de Turing editada. Una vez finalizados todos los pasos, en la sección Resultado se muestra si la máquina de Turing editada 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.


EjemploConceptos Teóricos