Page 78 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS

78

ENTREGA VII

GRAMÁTICAS LIBRES DEL CONTEXTO

Gramáticas libres del contexto estas gramáticas, conocidas también como gramáticas de tipo 2 o
gramáticas independientes del contexto, son las que generan los lenguajes libres o independientes
del contexto. Los lenguajes libres del contexto son aquellos que pueden ser reconocidos por un
autómata de pila determinístico o no determinístico. Es decir caracterizan a las cadenas que son
reconocidas por un autómata de pila.

A diferencia de las gramáticas regulares, estas no tienen restricciones respecto al lado derecho de
la gramática, para sus reglas de derivación o reescritura. Aunque sí se requiere que haya un solo
no terminal del lado izquierdo. Por ejemplo la siguiente gramática es una gramática independiente
del contexto, pero no lo es regular.

Independiente del contexto significa que como el lado izquierdo de cada regla de reescritura solo
puede contener un solo no terminal, la regla se aplica no importa donde se encuentre
(independiente del contexto donde r se encuentre) ese no terminal.

Al igual que las gramáticas regulares hay que hacer derivaciones, y se da el caso que no sabemos
cuál será el no terminal a reemplazar en un momento o paso especifico de la derivación.

Acá como ya dijimos se aplica la derivación por la derecha o por la izquierda,

Ejemplo. Gramática independiente del contexto:
S  ZMNZ

M  AMA

M  Z

N  BNB

N  Z

Si se aplica una regla de escritura situado al no terminal más a la izquierda:

S ZMNZ  ZAMANZ  ZAZANZ  ZAZABNZ ZAZABZBZ
Si se aplica una regla de escritura situado al no terminal más a la derecha:

S ZMNZ  ZMBNBZ ZMBZBZ  ZAMABZBZ  ZAZABZBZ

El orden no afectará el resultado de una gramática. Es claro que el grado de recurrencia de una
misma derivación puede alterar la cadena resultante pero no el patrón que siguen todas las cadenas
posibles.

Como toda gramática se definen mediante una cuádrupla G = (N, T, P, S), siendo

 N un conjunto finito de símbolos no terminales.
 T es un conjunto finito de símbolos terminales N ∩ T = ∅.
 P es un conjunto finito de producciones o reglas de derivación.
 S es el símbolo distinguido o axioma de inicio.