Tema 2.- Gramáticas independientes de contexto.
1. Derivación más a la izquierda (derecha)
2. Árbol de derivación.
3. Ambigüedad.
4. Simplificación de Gramáticas.
5. Formas Normales.
5.1. De Chomsky.
5.2. De Greibach.
Gramáticas independientes de contexto
A   : A  N,   V*
Derivación más a la izquierdas (derechas) : En todos los pasos de la
derivación se sustituye el no terminal más a la izquierda (derecha).
Ejemplo:
S  AB | BA | D
A  CAC | 0
B  CBC |1
C 0|1
D CCD|C
•Derivación más a la izquierdas
S  AB  CACB  0ACB  00CB 001B 0011
•Derivación aleatoria
S  AB  CACB  C0CB C0C1 00C1 0011
Árbol de derivación en G
Árbol que cumple:
1. Raíz etiquetada con S.
2. Nodos interiores etiquetados con auxiliares
3. Nodos hoja etiquetados con terminales o 
4. Nodo etiquetado con  es el único sucesor de su
predecesor.
5. Si un nodo está etiquetado con A y sus sucesores
con B1 B2 ... Bn entonces A  B1 B2 ... Bn  P
Subárbol de derivación en G
S
Cumple de 2 a 5
A
S  AB  CACB  0ACB  00CB 001B 0011
C A C
0
0
1
B
1
Ambigüedad
• G = (N, , P, S) es ambigua si existe x  * con más de un árbol de derivación.
Ejemplo: S  SS | 0
S
S
S
S
S
S
S
S
0
0
S
S
0
0
0
0
Un lenguaje es inherentemente ambiguo si toda gramática que lo genera es ambigua.
Ejemplo: 0+ no es inherentemente ambiguo (puede ser generado por S  SS | 0
y por S  0S | 0 ).
L = {0i 1j 2k : i = j  j = k} es inherentemente ambiguo.
Simplificación de Gramáticas Incontextuales
• Gramáticas equivalentes
G equivalente a G ’ si L(G) = L(G ’) ó L(G) = L(G ’) - {}
• Símbolos inútiles (no intervienen en la generación de palabras)
• No generativos

A  N, es generativo si     * con A  
G
• No alcanzables
A  N, es alcanzable si forma parte de forma sentencial
derivable desde S.
El orden de eliminación es importante
Ejemplo: S AB|a
A a
Dada una gramática G existe otra G’ equivalente a G
sin símbolos inútiles.
Producciones vacías.
• Cualquiera de la forma A  
•Si L(G) debe existir alguna producción A  
(Se puede conseguir que sea S  )
•Si  L(G) se puede conseguir una equivalente sin
producciones vacías.
Dada una gramática G existe otra G’con L(G’) =L(G)- {}
sin producciones vacías.
•Producciones unitarias.
• Cualquiera de la forma A  B
Dada una gramática G existe otra G’ equivalente a G sin
producciones unitarias.
•Proceso de simplificación.
1. Eliminación de Símbolos inútiles.
2. Eliminación de Producciones vacías.
3. Eliminación de Producciones unitarias.
4. Eliminación de Símbolos inútiles.
Simplificación de las gramáticas incontextuales.
Si L es un lenguaje incontextual no vacío  G de tipo 2 que lo genera,
con:
•Cada símbolo de G aparece en la derivación de alguna palabra del lenguaje.
•No hay reglas de la forma A  B con A, B N .
•Si   L se pueden eliminar todas las producciones de la forma A  .
Caso contrario se puede conseguir que la única regla de este tipo sea S   .
Eliminar no generativos en:
Eliminar lar regas unitarias en:
Aplicar los algoritmos anteriores a las gramáticas
1.
S  A|AAA|AA
A  Aba|Aca|a
B  Aba|Ab|
C  CAba|CC
D  CD|Cd|Cea
Eb
2.
Resolución de 2.
1. Eliminación símbolos no generativos
3. Eliminación reglas 
5. Eliminación reglas unitarias
2. Eliminación símbolos no accesibles
4. Eliminación símbolos no generativos
Descargar

Tema 2