Gramáticas Libres del Contexto

Gramáticas
Las gramáticas formales definen un lenguaje describiendo cómo se pueden generar las cadenas del lenguaje.
Una gramática formal es una cuadrupla G = (N, T, P, S) donde
    - N es un conjunto finito de símbolos no terminales
    - T es un conjunto finito de símbolos terminales 
   -  P es un conjunto finito de producciones
       Cada producción de P tiene la forma
    - S es el símbolo distinguido o axioma 
Restringiendo los formatos de producciones permitidas en una gramática, se pueden especificar cuatro tipos de gramáticas (tipo 0, 1, 2 y 3) y sus correspondientes clases de lenguajes.

Gramáticas libres del contexto (Tipo 2)
Estas gramáticas, conocidas también como 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.
Como toda gramática se definen mediante una cuadrupla G = (N, T, P, S), siendo
    - N es un conjunto finito de símbolos no terminales
    - T es un conjunto finito de símbolos terminales 
    - P es un conjunto finito de producciones
    - S es el símbolo distinguido o axioma 

En una gramática libre del contexto, cada producción de P tiene la forma

Es decir, que en el lado izquierdo de una producción pueden aparecer el símbolo distinguido o un símbolo no terminal y en el lado derecho de una producción cualquier cadena de símbolos terminales y/o no terminales de longitud mayor o igual que 1.
La gramática puede contener también la producción si el lenguaje que se quiere generar contiene la cadena vacía.