Gramáticas

Una gramática es un conjunto de reglas que sigue un lenguaje para la estructura de palabras válidas. Las gramáticas por lo regular producen cadenas o palabras que pertenecen a algún lenguaje, y la producción de estas palabras está determinada por reglas de sustitución bien definidas. A estas reglas también se les llama producciones. Dicho lo anterior, podemos decir que un lenguaje es descrito por una gramática $G$, donde $G$ es una túpla de cuatro elementos $G=(N,S,\Sigma,P)$, donde:

• $N$. Un conjunto de símbolos no terminales, que funcionan como variables a través de las reglas de producción. Son substituidas, en cada paso, por una secuencia de símbolos que pueden ser terminales, no terminales o una combinación de ambos.

• $S\in N$. Es el símbolo inicial del cual derivan las demás producciones por medio de las reglas de producción.

• $\Sigma$. Un alfabeto sobre el cual se generará el lenguaje. A los símbolos de este alfabeto se les llama terminales, ya que una vez que forman parte de la palabra producida, no son reemplazados por algún otro símbolo.

• $P$. Es el conjunto de reglas de producción, con el cual se generarán las posibles cadenas que integren el lenguaje.

Podemos pensar en las gramáticas como las reglas que estructuran el lenguaje. Es común que se utilicen letras mayúsculas para denotar a los símbolos no terminales y letras minusculas para denotar a los símbolos terminales. El lenguaje generado por una gramática $G$ comunmente se denota como $L(G)$.