Gramática Libre de 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. 

Las Gramáticas Libres de Contexto (Context-Free Languages) o CFL’s jugaron un papel central en el lenguaje natural desde los 50’s y en los compiladores desde los 60’s

Forman la base de la sintaxis BNF (Backus-Naur form), son actualmente importantes para XML y sus DTD’s (document type definition)

Son útiles para describir bloques anidados en lenguajes de programación ya que describen su sintaxis, además, son llamadas así porque el elemento no terminal del lado derecho se puede sustituir sin importar el contexto en que este.

           

Puede ser definida mediante la 4-tupla G = (N, T, P, S), siendo

            - N es un conjunto finito de símbolos no terminales (disjunto de T)

            - T es un conjunto finito de símbolos terminales

            - P es un conjunto finito de producciones o reglas gramaticales, de la forma A à a, donde A es un elemento de N y a es un elemento de (T U N)* (una secuencia posiblemente vacia de terminales y no terminales)

            - S es el símbolo inicial, distinguido o axioma del conjunto N