Gramática ambigua.
Una sentencia w se denomina ambigua si puede obtenerse por más de un árbol de derivación (o equivalentemente, más de una derivación más a la izquierda o más a la derecha).
Una gramática G se denomina ambigua si el lenguaje que genera contiene alguna sentencia ambigua.
Lenguaje inherentemente ambiguo
Un lenguaje se denomina inherentemente ambiguo si no existe una gramática no ambigua que lo genere.
3.3 Formas Normales de Chomsky.
Una GLC se dice que está en Forma Normal de Chomsky (FNC) si todas sus producciones son de la forma:
Excepcionalmente se permite la producción
La idea de la transformación de una gramática limpia a FNC se ejecuta en dos pasos:
·
- Hacer que en la parte derecha de las producciones de longitud mayor o igual que dos sólo haya terminales.
- Trocear estas producciones para que tengan longitud dos.
Algoritmo FNC:
1. Para cada producción de la forma 
(a) Para cada αi, si αi es terminal: 
- Se añade la producción Ca → a
- Se cambia αi por Ca en A → α1..αn
2. Para cada producción de la forma A → B1...Bm, m ≥ 3
(a) Se añaden (m-2) no terminales D1, D2, ..., Dm-2 (distintos para cada producción)
(b) La producción A → B1...Bm se reemplaza por A → B1D1, D1 → B2D2, ... Dm-2 → Bm-1Bm
3.4 Forma Normal de Greibach
Definición:
Una GLC se dice que está en Forma Normal de Greibach (FNG) si todas sus producciones son de la forma:
Excepcionalmente se permite la producción 
¿Hasta qué profundidad deberíamos explorar el árbol de expansión para decidir si una cadena w de longitud n es generada o no por una gramática en FNC/FNG?
Nota:
Informaciòn recopilada de las siguientes ligas:
José Miguel Puerta, Antonio Fernández Caballero, Departamento de Informática Universidad de Castilla-la Mancha en:
GRAMATICAS LIBRES DE CONTEXTO
ResponderEliminarLas gramáticas libres de contexto amplían la capacidad para especificar lenguajes al incluir algunos lenguajes que no son reconocidos por un autómata finito.
Las gramáticas libres de contexto son útiles para describir expresiones aritméticas que tengan una anidación arbitraria de paréntesis balanceados y estructuras de bloque en los lenguajes de programación.
ARBOLES DE DERIVACIÓN
Un árbol de derivación permite mostrar gráficamente cómo se puede derivar cualquier cadena de un lenguaje a partir del símbolo distinguido de una gramática que genera ese lenguaje.
Un árbol es un grafo dirigido acíclico en el cual cada nodo se conecta con un nodo distinguido, llamado nodo raíz, mediante un único camino.
Un nodo n1 se dice descendiente de otro nodo n2 si se puede llegar a n1 a partir de n2. El nodo raíz no es descendiente de ningún nodo, y los nodos que no tienen descendientes se denominan hojas. El resto de los nodos sedenominan nodos interiores. Para cada cadena del lenguaje generado por una gramática es posible construir (al menos) unárbol de derivación, en el cual cada hoja tiene como rótulo uno de los símbolos de la cadena.
FORMAS NORMALES DE CHOMSKY
ResponderEliminarProposición 3.1 Toda gramática libre de contexto G=(V,T,P,S) que no genere a la palabra vacía se puede transformar en una gramática libre de contexto
G'=(V',T,P',S') en forma normal de Chomsky. En efecto, dada una gramática G, apliquemos el último procedimiento de la sección anterior para transformar a G en una gramática G'' sin variables inútiles ni producciones vacías ni producciones unitarias equivalente a G.
A las producciones que quedasen de la forma con y las dejamos sin cambio alguno. A cada producción de la forma , con y , la transformamos en una sucesión de producciones de la forma siguiente: A cada símbolo terminal que aparezca en la palabra le asociamos una variable nueva Xa e incorporamos la producción . Así pues las producciones que no sean de la forma con X variable y a terminal, han de ser de la forma , con todos variables. Para cada una de estas últimas producciones introducimos k-2 nuevas variables e incorporamos la sucesión de producciones