Para algunas asignaturas, tales como Teoria de Autómatas y Lenguajes Formales o Procesadores de Lenguajes, se pueden plantear preguntas cuya respuesta es una gramática de contexto libbre o regular. Por ejemplo:

Para este tipo de problemas se ha definido un plugin que reconoce cualquier respueta dada por un alumno, sin que la gramática prpuesta deba ser identica a la propuesta, sino simplemente equivalente, es decir, que genere el mismo lenguaje.

En el ejemplo anterior la siguiente gramática sería una respuesta correcta:

A -> Aa
A -> a

Pero tambien lo seria la gramática

A -> aA
A -> a

e incluso otras gramáticas definidas mediante otros simbolos no terminales, o bien ambiguas, tales como:

S -> SS
S -> a

El profesor debe proporcionar una gramática que servirá como patron de comparación; sin embargo para reconocer si la respuesta de un alumno es correcta, no es suficiente por tanto una correspondencia sencilla entre el patrón y la respuesta. Es necesario comprobar mediante un procedimiento que los lenguajes generados por ambas gramaticas son equivalentes. En el caso general se ha demostrado que la equivalencia de gramáticas es una cuestión indecidible, es decir, que en el caso general no existe ningún algoritmo que nos diga si una gramática es o no equivalente a otra. Sin embargo, para los casos en llos que la gramática tiene pocas reglas, se puede resolver el problema mediante fuerza bruta. Para ello se generan todas las posibles cadenas del lenguaje a partir de la gramática de la respuesta hasta una cierta longitud y profundidad del árbol de derivaciones; y se comprueba que todas ellas están incluidas en el conjunto de cadenas generadas por la gramatica propuesta como patrón hasta con una longitud maxima y profundidad del árbol superior; y viceversa.

En caso de que las gramáticas no sean equivalentes, durante el proceso de búsqueda de la equivalencia, el plugin localiza las posibles cadenas de caracteres que diferencian a ambas gramáticas. El plugin tambien comprueba si la gramatica propuesta es o no ambigua.

Para el ejemplo anterior, el profesor puede proporcionar varios patrones de reconocimiento:

@GramaticaEquivalente
A->Aa
A->a

@ErrorSintactico

@ErrorGramaticaNoValida

El primer patrón se verifica cuando la gramática de la respuesta del alumno coincide con la gramática propuesta por el profesor. El segundo patrón se verifica cuando la respuesta del alumno contiene una gramática que esta mal escrita, al no seguir las reglas sintacticas para escribir gramáticas que se detallan al final de esta página. El tercer patrón corresponde a una gramática no valida, es decir, a una gramática que contiene simbolos no finalizables o simplemente no está completa.