Usamos el símbolo *⇒ para decir "deriva".
Si αAλ &isin (Σ ∪ N)*
y A→δ ∈ P es una producción de G
entonces αAλ ⇒G αδλ
Omitimos el subíndice G cuando ello no se presta a confusión.
También usamos los operadores ⇒*, ⇒+, y ⇒k, los cuales tienen los significados esperados: deriva en cero o más pasos, deriva en uno o más pasos, y deriva en k pasos.
Derivación
Una derivación de una sentencia ω es la secuencia de sustituciones de no-terminales que, partiendo del símbolo inicial S, produce como resultado ω.
 | Falta ejemplo aquí |
Derivación Izquierda/Derecha
Una derivación izquierda/derecha es la que se obtiene sustituyendo primero el no-terminal más a la izquierda/derecha en cada forma sentencial. Las formas senteciales así obtenidas se llaman formas sentenciales izquierdas/derechas.
Como una Derivacion izquierda/derecha indica cuál símbolo no-terminal se substituye en cada paso de una Derivacion, entonces si le damos un número distinto a cada producción de la gramática es posible representar una derivación dando solo la secuencia de números de las producciones que se emplearon en cada paso.
Forma Sentencial
Una forma sentencial de una Gramatica G=(Σ N, P, S) se define recursivamente:
- S, el símbolo inicial, es una forma sentencial.
- Si αβλ es una forma sentencial, y β→δ ∈ P es una producción de G,
entonces αδλ es también una forma sentencial de G
Es decir, una forma sentencial es cualquier secuencia de símbolos terminales y no- terminales ω ∈ (Σ ∪ N)* tal que S ⇒*ω (se deriva en cero más pasos a partir de S).
Para las Gramáticas Libres de Contexto, β es siempre un no-terminal.
Forma Sentencial Izquierda/Derecha
Una forma sentencial es izquierda (derecha) si es producto de una Derivacion izquierda (derecha).
Gramatica Ambigua
Una gramática es ambigua si existe más de una Derivacion para la misma Forma Sentencial.
| Ejemplo? |
