Se deben traducir las cadenas de L de tal forma que por cada 0 se obtenga una F y por cada 1 una T:
A continuación se describen los pasos a seguir para editar el autómata finito traductor determinístico anteriormente descripto utilizando Minerva.
Edición de un autómata
finito traductor determinístico
Primero, se debe acceder
a la ventana de edición de atuómatas finitos traductores
determinísticos desde el menú principal por medio de las
opciones
las opciones Autómatas ->
Finito -> Traductor -> Determinístico(o utilizando la tecla
rápida F5). 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 traductor determinístico 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 traductor determinístico.
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 obtenemos el siguiente resultado.
Ingreso de los símbolos
del alfabeto de entrada y de salida
Antes de asociar los símbolos
correspondientes a las transiciones, los mismos deben ser ingresados al
alfabeto de entrada y al de salida. Sin embargo, las transiciones (sin
sus símbolos) pueden ser ingresadas previamente. Note que a medida
que ingresa nuevos símbolos a los alfabetos, la definición
formal se actualiza automáticamente.
Pero ahora, defina el alfabeto
de entrada y el de salida 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 los cuadros de texto correspondiente y
presione la tecla ENTER o bien el botón Agregar cada vez
que incorpore un símbolo. 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 definidos los alfabetos completos, presione el botón
Cerrar.
Ingreso de las transiciones
Para ingresar las transiciones
que conforman el autómata finito traductor determinístico,
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 y de salida.
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 los símbolos. Si desea incorporar mas de una
transición entre dos estados, presione el botón
, si fuese necesario eliminar alguna transición ingresada, efectúe
click sobre alguno de los símbolos que la conforman y presione el
botó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 traductor determinístico 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 traductor determinístico 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 y qué resultado produce su traducción.
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 001111
(equivalente
a 0214)
se puede comprobar que el autómata finito traductor deteminístico
editado la reconoce y produce la salida aaaaabbbcbc (equivalente
a a5b2(bc)2
)como resultado de la traducción. 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 traductor determinístico
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 hecho. Por ejemplo, al ingresar la cadena 01111 se puede observar que el autómata finito traductor determinístico editado no la reconoce.
Reconocimiento por pasos
Para comprobar si el autómata
finito traductor determinístico
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 de
la expresión regular a partir del autómata finito traductor
determinístico editado
Con el uso de Minerva
se puede obtener la expresión regular a partir del autómata
finito traductor determinístico 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 a la parte reconocedora del autómata finito traductor
determinístico editado. Para el ejemplo dado, el resultado es el
siguiente.
Si observa, el resultado
obtenido, eliminando los paréntesis redundantes es 00(0)*1111(11)*+00(0)*1111(11)*0(0)*.
Obtención de
la gramática regular a partir del autómata finito traductor
determinístico editado
La última operación
que se puede efectuar es la de obtener la gramática regular a partir
del autómata finito traductor determinístico editado, esto
se lleva a cabo presionando el botón
que se encuentra en la barra de herramientas. Con esto, se abrirá
una nueva ventana de edición de gramáticas regulares que
muestra la correspondiente a la parte reconocedora del autómata
finito traductor determinístico editado. Para el ejemplo dado, el
resultado es el siguiente.