Consultas sobre el Práctico 6

Buenas tardes Rodrigo, es lo segundo. Una gramática regular es una "gramática libre de contexto con restricciones"; pueden ser en forma "lineal izquierda" o "lineal derecha", como vos bien decís.

Dicho de otra forma, hay gramáticas libre de contexto (que no son Gramáticas regulares) que generan lenguajes regulares, por ejemplo:

$S \longrightarrow aX | \epsilon$
$X \longrightarrow Sa$

Esa gramática (que no es lineal izquierda ni lineal derecha) es una gramática libre de contexto que genera el lenguaje $L((aa)^*)$, que claramente es regular. En este post hay un poco más de consideraciones al respecto.

Lo importante es que, por más que las GLCs puedan generar lenguajes regulares, nosotros les exigimos que siempre usen el formalismo de mejor complejidad posible. Por lo tanto, si el lenguaje es regular, tienen que hacer una gramática regular; y si es libre de contexto y no regular, tienen que hacer una gramática libre de contexto.

Saludos,
Santi