Ejemplo de Expresión Regular

Se va a mostrar el uso de Minerva en expresiones regulares 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}

La expresión regular que lo describe es (0+1)*(00+11)(0+1)*

A continuación se describen los pasos a seguir para editar la expresión regular anteriormente descripto utilizando Minerva.

Edición de una expresión regular
Primero, se debe acceder a la ventana de edición de atuómatas finitos no determinísticos desde el menú principal por medio de las opciones las opciones Autómatas -> Finito -> Expresión Regular (o utilizando la combinación de teclas rápidas CTRL-E). De esta forma, se muestra un diálogo en donde se puede comenzar con la edición de la expresión regular.


 

Ingreso de la expresión regular
Ingrese la expresión regular en el cuadro de texto correspondiente.

Recuerde que la operación de concatenación se puede expresar tanto escribiéndola en forma explícita por medio del ingreso del símbolo ' . ' como en forma implícita, por la omisión del mismo. A continuación se dan dos expresiones regulares equivalentes.
    exp1 = (a+bc)   ;  exp2 = (a+b.c)
 

Ingreso de los símbolos
Antes de poder obtener el autómata finito no determinístico con transiciones vacías asociado a la expresión regular editada, es necesario ingresar los símbolos correspondientes a la misma. Sin embargo, la expresión regular puede ser ingresada previamente.
Pero ahora, defina los símbolos del alfabeto 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 completo, presione el botón Cerrar.
 

Operaciones sobre la expresión regular editada

Obtención del autómata finito no determinístico con transiciones vacías asociado
La operación que se puede efectuar sobre la expresión regular editada es la obtención del autómata finito no determinístico con transiciones vacías asociado. 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 con transiciones vacías 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 no determinístico equivalente al obtenido a partir de AFND_E presionando el botón 
correspondiente a esta última ventana abierta. El resultado de efectuar esta operación es el siguiente.

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

Una vez obtenido este resultado, puede obtener el auómata finito determinísitco con cantidad mínima de estados equivalente al obtenido a partir de AFND presionando el botón  correspondiente a esta útlima ventana abierta. El resultado de efectuar esta operación es el siguiente.

Por último, pude ver que si obtiene la expresión regular asociada a este autómata presionando el botón  , el resultado es el siguiente.

Si observa la expresión regular resultante eliminando los paréntesis redundantes, resulta: (00+(1+01)(01)*(1+00))(0+1)* que es equivalente a la expresión regular dada como ejemplo.


Conceptos Teóricos