Ejemplo de la Prueba de que un Lenguaje no es Regular


A continuación se describen los pasos que se deben seguir para probar que un lenguaje dado como ejemplo no es regular utilizando Minerva. La ventana en donde se utiliza el lema Pumping para probar que un lenguaje no es regular se accede desde el menú principal por medio de la opción Lema Pumping -> Prueba de Lenguajes no Regulares (o utilizando la combinación de teclas rápidas CTRL-P).

Luego para trabajar con un ejemplo se debe presionar el botón  , con lo cual, el cuadro de texto destinado al ingreso de un nuevo lenguaje a probar, pasa a ser una lista en donde se puede elegir uno de los ejemplos.

Para comenzar a trabjar el usuario debe seleccionar un lenguaje de los dados como ejemplo en la lista de selección que se encuentra en la sección de Definiciones de la vista.

Luego de haber seleccionado el lenguaje se debe definir cuál va a ser el valor de la variable n; la definición de la misma debe corresponderse con un factor de la variable utilizada como superíndice en el lenguaje.  Por ejemplo, para el lenguaje seleccionado  apbp+1 el valor que puede tomar n es p,2*p, p/2, etc., pero no se le puede asignar valores como p+1 ó p/2+2.

Luego de haber seleccionado el lenguaje con que se desea trabajar y el valor de la variable n, para proseguir con la prueba se debe presionar el botón Continuar; esta acción conduce a que se muestren las posibles subcadenas v´s.

Una vez que se tienen las subcadenas v´s se debe seleccionar una de ellas para continuar con la prueba.  Esta acción conduce a que se muestren los valores que toman las subcadenas u, v y w.

La prueba de que un lenguaje es no regular se lleva a cabo si es posible encontrar un valor al cual se puede elevar la subcadena v, para formar una cadena que no forme parte del lenguaje dado.  Por lo tanto es necesario, en este paso de la prueba, ingresar un valor de i, para el cual la cadena resultante no pertenezca al lenguaje ingresado.

Luego de haber ingresado el valor correspondiente a la i, se debe presionar el botón Ejecutar para obtener el resultado.  Si la cadena resultante uviw no corresponde al lenguaje, la herramienta informa que el lenguaje no es regular; en caso contrario, el usuario debe ingresar otro valor de i.

Como se puede observar, el lenguaje seleccionado resulta ser no regular dado que la cadena resultante ap+4kbp+1 no pertenece al lenguaje porque la cantidad de a´s no es la cantidad de b´s más uno para cualquier valor que puedan tomar k.


Conceptos Teóricos