¿GR o GLC?

¿GR o GLC?

de Santiago Agustín Silveira Pérez -
Número de respuestas: 3

Hola.

En el ejercicio 4 pide indicar si se trata de una gramática regular o una gramática libre de contexto. Y me surgió una
duda con el 1. La primer regla es S -> Ab | aB. Yo pienso que es una gramática regular (no es lineal porque no están
todas las variables a la derecha o todas las variables a la izquierda, pero no quita que sea regular). ¿Esto es correcto?

Saludos.

Santiago.

En respuesta a Santiago Agustín Silveira Pérez

Re: ¿GR o GLC?

de Santiago Gongora -

Buen día Santiago, espero estés bien.

Veo que entendés bien las definiciones de lineal izquierda y lineal derecha. Tu duda es bien de nomenclatura.

Las "gramáticas regulares" son un formalismo que tienen el mismo poder de cómputo que una expresión regular (y claramente el mismo que un autómata finito). Por definición, esas gramáticas regulares son una de las siguientes dos:

  • gramática lineal izquierda, donde los símbolos no-terminales aparecen siempre al inicio de la producción

  • gramática lineal derecha, donde los símbolos no-terminales aparecen siempre al final de la producción

Si googleás por ahí podrías llegar a encontrar que hay algún detalle formal sobre el tipo de lenguaje, cuando se habla del lenguaje generado por una "gramática lineal" a secas (sin "izquierda" o "derecha"), pero todo eso está por fuera del alcance del curso.

Así que, concretamente, si les pedimos una "gramática regular", les estamos pidiendo que construyan una gramática lineal izquierda o una gramática lineal derecha.

Espero que haya quedado claro y si no, como siempre, preguntá de nuevo :)


Saludos,
Santi