Ejemplo de Máquina de Turing Determinística

Se va a mostrar el uso de Minerva en máquinas de Turing determinísticas mediante el desarrollo de un ejemplo.
El lenguaje con que se va a trabajar es

A continuación se describen los pasos a seguir para editar la máquina deTuring determinística anteriormente descripta utilizando Minerva.

Edición de una máquina de Turing determinística
Primero, se debe acceder a la ventana de edición de máquinas de Turing determinísticas desde el menú principal por medio de los ítems Autómatas -> Máquina de Turing -> Determinística(o utilizando la tecla rápida F11). 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 la cantidad de cintas que se desea utilizar, para el ejemplo dado, ingrese el número 2.


 

Luego, presione ENTER o el botón Aceptar, de esta forma, se abrirá un nuevo diálogo en el que debe ingresar el nombre del archivo en donde se desea guardar la máquina de Turing 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 de la máquina de Turing 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 correspondiente y tipear el símbolo o estado. Para ingresar el movimiento, presione click sobre la celda de movimiento correspondiente 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 incorporar 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.
Una vez completadas todas las celdas de la tabla que conforma la función de transición, el resultado será el siguiente.


 

Definición del estado inicial y el estado final
Antes de poder efectuar alguna de las operaciones que se pueden llevar a cabo por medio de Minerva con la máquina de Turing 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, presione el botón  con lo cual se abre un diálogo en donde se pueden setear estos estados.

El nombre del estado inicial (e0) debe ser ingresado en el cuadro de texto etiquetado como Estado Inicial y el estado final (e4) se incorpora tipeando este nombre 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 el estado final, 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 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.
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 que forman parte de la máquina de Turing, presione 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 determinística.

Operaciones sobre la máquina de Turing determinística editada

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. 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.
En esta ventana ingrese la cadena que desea probar en el campo de texto correspondiente. Si, por ejemplo, ingresa la cadena abcab se puede comprobar que la máquina de Turing determinística editada 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 la máquina de Turing determinística editada 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.

A su vez, se mostrará la configuración de las cintas que conforman la máquina de Turing en un nuevo 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 bcab se puede observar que la máquina de Turing determinística editada no la reconoce.

Nuevamente, se puede observar cómo quedan las cintas tras esta ejecución.


 

Reconocimiento por pasos
Para comprobar si la máquina de Turing determinística editada 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, 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. 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.

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.


Conceptos Teóricos