Gramaticas Regulares

GRAMATICAS LIBRES DE CONTEXTO (GLC)

Una Gramática Libre de Contexto es una tupla con 4 parámetros :
G = (V,T,P,S)
• V – conjunto de símbolos variables
• T – conjunto de símbolos terminales
• S ∈ V, símbolo inicial
• P – conjunto de reglas de producción :
A → α , con α sucesión de símbolos de V ∪ T, eventualmente vacía (α = ε)
¿Qué es una gramática?
• Modelo de estructuras recursivas.• Definición de reglas para representar las expresiones de los lenguajes.
• Especificación rigurosa y explicita de estructura de un lenguaje.
Características:
• Ausencia de ambigüedad, por tanto bien definidas.
• Rigurosas (claridad, explicitud).
• Facilitan evaluación: comprobar, conclusiones, derivar.
• Hacer predicciones: generalización.
• Desarrollo de aplicaciones.Las gramáticas generativas son modelos matemáticos finitos que nos permiten generar las
cadenas o palabras de un lenguaje finito o infinito.
Según la Jerarquía de Chomsky: las gramáticas generativas se clasifican en 4 tipos. Esta
clasificación es inclusiva, es decir tipo 3 ⊂ tipo 2 ⊂ tipo 1 ⊂ tipo 0




ARBOLES DE DERIVACION

Un árbol de derivación permite mostrar gráficamente cómose 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 conjunto de puntos, llamados nodos, unidos por líneas, llamadas arcos. Un arco conecta dos nodos distintos. Para ser un árbol un conjunto de nodos y arcos debe satisfacer ciertas propiedades:

Hay un único nodo distinguido, llamado raíz (se dibuja en laparte superior) que no tiene arcos incidentes.
Todo nodo c excepto el nodo raíz está conectado con un arco a otro nodo k, llamado el padre de c (c es el hijo de k). El padre de un nodo, se dibuja por encima del nodo.
Todos los nodos están conectados al nodo raíz mediante un único camino.
Los nodos que no tienen hijos se denominan hojas, el resto de los nodos se denominan nodos interiores.

 Propiedades de un árbol de derivación.

Sea G = (N,T,S,P) una gramática libre de contexto, seauna variable. Diremos que un árbol TA = (N,E) etiquetado es un árbol de derivación asociado a G si verifica las propiedades siguientes:

·         La raíz del árbol es un símbolo no terminal
·         cada hoja corresponde a un símbolo terminal o λ.
·         cada nodo interior corresponde a unsímbolo no terminal.

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.


 

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.Si un nodo está etiquetado con una variable X y sus descendientes (leídos de izquierda a derecha) en el árbol son X1,…,Xk , entonces hay una producción X → X1…Xk en G.

Sea G=(N,T,S,P) una GLC. Un árbol es un árbol de derivación para G si:
1. Todo vértice tiene una etiqueta tomada de 
 2. La etiqueta de la raíz es el símbolo inicial S
3. Los vértices interiores tienen etiquetas de N
4. Siun nodo n tiene etiqueta A y n1n2...nk respectivamente son hijos del vértice n, ordenados de izquierda a derecha, con etiquetas x1,x2..xkrespectivamente, entonces: A→ x1x2...xk debe ser una producción en P
5. Si el vértice n tiene etiqueta λ, entonces n es una hoja y es el único hijo de su padre.


Árbol de derivación. Ejemplo
Sea G=(N,T,S,P) una GLC con P: S→ ab|aSb
  
La derivación de lacadena aaabbb será: 
y el árbol de derivación:




NORMAL 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...