Gramática

gramática.
1. f. Ciencia que estudia los elementos de una lengua y sus combinaciones.

Diccionario de la Real Academia de la Lengua Española

Gramática Formal

En informática y linguística, una gramática es un conjunto de reglas (usualmente recursivas) que describen de manera relativamente breve las cadenas, frases o secuencias válidas en un Lenguaje. Además, una gramática describe la estructura jerárquica o sintáctica de las frases de un Lenguaje.

Una gramática es un conjunto de reglas de la forma:

α → β

por ejemplo:

expre → expre + expre
expre → a

el operador → puede leerse como "tiene esta forma" o "es reemplazable por". Cada una de las reglas se llama una producción.

Definición formal

Una gramática es una tupla G=(Σ,N,P,S), donde:

1. Σ es un alfabeto, el cual llamamos de símbolos terminales
2. N es un conjunto de símbolos no-terminales tal que
   N ∩ Σ = Ø
3. P es un conjunto de producciones, que son pares (α, β) tal que:
   α ∈ (Σ ∪ N)^* N (Σ ∪ N)^*
   y
   β ∈ (Σ ∪ N)^*
4. Un símbolo S ∈ N, que es destacado como símbolo inicial

Forma de Escribir las Producciones

Frecuentemente escribimos las producciones en la forma:

α → β

Lado Izquierdo y Derecho de una Producción

Dada una producción

α→β

llamamos a α a el lado izquierdo de la producción, y a β el lado derecho de la producción.

Derivación

Usamos el símbolo *⇒ para decir "deriva".

Si αAλ ∈ (Σ ∪ 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:

1. S, el símbolo inicial, es una forma sentencial.
2. 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?

Lenguaje Generado por una Gramática

El lenguaje generado por una gramática es el conjunto de todas formas sentenciales de la gramática compuestas por solo no-terminales.

El lenguaje generado por una gramática es el conjunto de todas les secuencias de símbolos terminales que pueden ser derivadas por la gramática en un número finito de pasos.

Si G = (Σ, N, P, S),
entonces
L _G = { ω ∈ Σ^* | S ⇒^* ω }