- S es el símbolo distinguido o axioma
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.