Gramatica libre de contexto

CIENCIAS DE LA COMPUTACION I 2013

1

GRAMATICAS LIBRES DEL CONTEXTO - BNF
Estas gramáticas, conocidas también como gramáticas de tipo 2 o gramáticas independientes
del contexto, son las quegeneran 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.
Comotoda 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
N∩T=∅
- P es unconjunto finito de producciones
- S es el símbolo distinguido o axioma S ∉ (N ∪ T)
En una gramática libre del contexto, cada producción de P tiene la forma
A ∈ N ∪ {S}
A→ω
ω ∈ (N ∪ T)* - {ε}
Esdecir, 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 noterminales de longitud mayor o igual que 1.
La gramática puede contener también la producción S → ε si el lenguaje que se quiere
generar contiene la cadena vacía.
Los ejemplos mostrados a continuacióncorresponden a los lenguajes libres del contexto que
fueron introducidos en los ejemplos 1, 2 y 3 del apunte de autómatas de pila.
Ejemplo 1:
La siguiente gramática genera las cadenas del lenguajeL1 = {wcwR / w ∈ {a, b}* }
G1 = ({A}, {a, b, c}, P1, S1), y P1 contiene las siguientes producciones
S1 → A
A → aAa
A → bAb
A →c
Ejemplo 2:
La siguiente gramática genera las cadenas dellenguaje L2 = {0i 1i+k 2k 3n+1 / i, k, n ≥ 0 }
Casos
Cadenas de L2
si n, i, k > 0
0i 1i+k 2k 3n+1
si n=0 y i, k > 0
0i 1i+k 2k 3
si i=0 y n, k >0
1k 2k 3n+1
si k=0 y n, i >0
0i 1i 3n+1
si n, i=0 yk >0
1k 2k 3
si n, k=0 y i >0
0i 1i 3
si i, k =0 y n >0
3n+1
si n,i,k=0
3
G2 = ({A, B, C}, {0, 1, 2, 3}, P2, S2), y P2 contiene las producciones

CIENCIAS DE LA COMPUTACION I 2013
S2 →...