Prueba de Lenguajes no Regulares mediante el uso del Lema Pumping


El lema Pumping se puede utilizar para probar que ciertos lenguajes no son regulares.  A la ventana que permite llevar a cabo esta operación se accede desde el menú principal por medio de las opciones Lema Pumping -> Prueba de Lenguajes no Regulares (o utilizando la combinación de teclas rápidas CTRL-P).


Barra de herramientas
En la parte superior de la ventana se encuentra una barra de herramientas que contiene 3 botones cuya funcionalidad se describe a continuación.

Ayuda
Presionando este botón se puede acceder a esta página de ayuda.

Salir
Presionando este botón se cierra la ventana.

Ejemplos
Presionando este bóton se intercambia el modo de operación de modo edición a modo ejemplos.

Modos de Operación
Minerva permite aplicar el lema Pumping, como medio de prueba, tanto en lenguajes ingresados por el usuario como para ciertos lenguajes dados como ejemplos; los lenguajes ingresados deben respetar el formato anbn.  Para intercambiar entre los dos modos de operación que se proveen se debe presionar el botón  .  Cuando la ventana se abre se muestra la misma en el modo de operación de edición, es decir, se puede ingresar un lenguaje nuevo para ser probado.

Edición
El usuario debe ingresar el nuevo lenguaje en el campo de texto que se rotula como Ingrese el lenguaje a probar, respetando el formato anbn. Los superíndices se escriben manteniendo la tecla ALT presionada durante el ingreso de los mismos.

Luego de haber ingresado 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 ingresado  ap/2bp 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 ingresado 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 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 ingresado resulta ser no regular dado que la cadena resultante a3p/2-2jbp+2k no pertenece al lenguaje porque la cantidad de a´s no es la mitad de la cantidad de b´s para cualquier valor que puedan tomar j y k.
 

Ejemplos
Para trabajar con lenguajes que se dan como ejemplos se debe presionar el botón  , con lo cual se muestra una lista en donde se puede seleccionar un lenguaje entre los dados.

Para ver la aplicación del lema Pumping sobre uno de los lenguajes dados como ejemplos ir a ejemplo.


Ejemplo Conceptos Teóricos