Ejemplo de Gramática Libre del Contexto

Se va a mostrar el uso de Minerva en gramáticas libres del contexto mediante el desarrollo de un ejemplo.
El lenguaje con que se va a trabajar es L = {wcwR / w Î {a, b}* }, y a continuación definimos formalmente la gramática libre del contexto que lo describe.

    G = ({A}, {a, b, c}, P, S),  y P contiene las siguientes producciones

   { S ->A
     A -> aAa
     A -> bAb
     A ->c }

A continuación se describen los pasos a seguir para editar la gramática anteriormente descripta utilizando Minerva.

Edición de una gramática
Acceder a la ventana de edición de gramáticas desde el menú principal por medio de las opciones las opciones Gramáticas ->Libre del Contexto (o utilizando la combinación de teclas rápidas CTRL-L). 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 la gramática a generar.

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 gramática.


 

Ingreso de las reglas de producción
Las reglas de producción que forman parte de la gramática se deben escribir en los campos de texto dentro del recuadro que se titula Regla de Producción, en el primer campo se ingresa el lado izquierdo de la misma y en el segundo el lado derecho.  Una vez escrita la regla presionar sobre el botón Agregar para ingresar la nueva regla de producción.

De esta forma se deben ingresar todas las reglas de producción, al finalizar el ingreso de las mismas se pueden observar actualizados los datos correspondientes a los conjuntos de símbolos terminales y no terminales.


 

Operaciones sobre la gramática editada

Generación de cadenas
Una de las operaciones que se pueden llevar a cabo es la generación de cadenas a partir de las reglas de producción de la gramática para comprobar si estas reglas describen el lenguaje deseado.  Para llevar a cabo esta operación se tiene destinada una parte de la ventana en donde se edita la gramática rotulada con Generar, si en esa parte de la ventana se presiona sobre el botón Nueva cadena se muestra una cadena que pertenece al lenguaje descripto por la gramática.

Si se desean ver las reglas de producción que derivaron a la cadena abcba, se debe seleccionar la misma y presionar el botón derecho del mouse sobre ella.  Con dicha acción se muestra un menú con dos opciones, si se selecciona Arbol de derivación se muestra un diálogo con todas las reglas utilizadas para generar dicha cadena.


 

Verificación de si una cadena es generada por la gramática
Otra operación que se puede efectuar la verificación de si una cadena dada es generada por la gramática.  Para llevar a cabo esta operación se debe seleccionar el panel que permite ingresar una cadena a ser reconocida, dicha selección se lleva a cabo haciendo click sobre la etiqueta Reconocer. El panel seleccionado posee un campo de texto en donde se debe ingresar la cadena a ser reconocida.

Una vez que se ingresó la cadena ababcbaba se debe presionar sobre el botón Reconocer, esta acción lleva a cabo la comprobación de si existe un árbol de derivación que pueda generar la cadena dada.  Dado que la cadena ingresada pertenece al lenguaje descripto por la gramática, se muestra un diálogo con dicho árbol de derivación.

Si en cambio ingresamos la cadena abbcaba, que no pertenece al lenguaje, se muestra un mensaje que informa esta situación.


Conceptos Teóricos