Gramática

Definición: $$G = (V_N, V_T, P, S_0)$$ - ${V_N}$ es el conjunto finito no vacío de símbolos no terminales. Instrumentales, no aparecen en la cadena final. - ${V_T}$ es el conjunto finito no vacío de símbolos terminales. Son lo que aparecen en la cadena final. - P: es un conjunto finito de pares ordenados de la forma $(\alpha, \beta)$ tales que: - $\alpha \in (V_N \cup V_T)^ - V_T^$ ($\alpha$ no es vacío, está compuesto por terminales y no terminales y no puede ser solo terminales) - $\beta \in (V_N \cup V_T)^*$. ( $\beta$ es o bien vacío, o uno o más símbolos terminales y no terminales) - ${S_0}$ es el símbolo inicial, o la frase sintáctica raíz de la gramática. Es una secuencia que no puede ser dividida mediante las reglas definidas por $P$. Este símbolo se utiliza como punto de partida para construir otras estructuras en la lengua formal.

Ejemplo:] Números binarios

La gramática más simple que genera todos los números binarios: - $V_N = {S_0, S}$ - $V_T = {0, 1}$ - $P = {S_0 \rightarrow S, S \rightarrow 0S, S \rightarrow 1S, S \rightarrow \epsilon}$

Ejemplo de derivación para "101":

${S_0} → S → 1S → 10S → 101S → 101$

[!example] Paréntesis balanceados Gramática que genera todas las expresiones de paréntesis correctamente balanceados: - $V_N = {S_0, S}$ - $V_T = {(,)}$ - $P = {S_0 \rightarrow S, S \rightarrow (S), S \rightarrow SS, S \rightarrow \epsilon}$

Ejemplos de cadenas válidas: - () - (()) - ()()

Ejemplo de derivación para "(())":

${S_0} → S → (S) → ((S)) → (())$

Derivación directa

[!info] Derivación Sean y y δ $\in$ $(V_N \cup V_T)^$, se dice que existe una derivación directa* de y en δ si y = y₁$\alpha$y₂, δ = y₁βy₂ y en G existe la regla $\alpha$ → β.

Se denota este hecho por y ⇒ δ.

Traducción: Si tienes una cadena y y puedes cambiar una parte de ella ($\alpha$) usando una regla de la gramática ($\alpha \to \beta$), obtienes una nueva cadena $\delta$. Este cambio se llama derivación directa y se escribe como y⇒δ.

[!example] Ejemplo 1 Sea la gramática G = ({S, A, B, D}, {a, b, c, d}, P, S), donde P es el conjunto de reglas: 

S → Abc       cD → a
Ab → bA       A → dcB 
Ab → BcD      Ba → d
Ab → cA

Son derivaciones directas:

cDb__Ab__db ⇒ cDb__BcD__db b__cD__ab ⇒ b__a__ab Ab__c ⇒ __BcD__c __Ab__c ⇒ __dcB__bc __Ab ⇒ cA

Derivación con múltiples pasos

[!info] Derivación en múltiples pasos Sean y y δ ∈ ($V_N ∩ V_T$)*. Diremos que existe una derivación de y en δ si existen δ₁, ..., δₙ tales que y ⇒ δ₁ ⇒ ... ⇒ δₙ = δ. Se denota este hecho por y ⇒⁺ δ.

Para incluir el caso de cero pasos, es decir, que no se aplique ninguna regla, se generaliza la notación de una derivación a y ⇒* δ.

[!example] Ejemplo 2 En la gramática del ejemplo 1 se puede escribir aBAbcd ⇒⁺ aBdcd, pues se cumple que:

aB__Ab__cd ⇒ aB__Bc__Dcd ⇒ aB__Ba__cd ⇒ aB__d__cd

También se puede escribir aBAbcd ⇒ aBdcd porque, como puede observarse en sus respectivas definiciones, ⇒ incluye a ⇒⁺.

Oraciones

Dada una gramática G = ($V_N, V_T$, P, S) y una cadena α ∈ ($V_N, V_T$), se dice que α es una forma oracional* en G si se cumple que S ⇒⁺ α.

[!example] Ejemplo 3 Sea la gramática G = ({S, A, B, D}, {a, b, c, d}, P, S), donde P es el conjunto de reglas: 

S → Abc       cDc → Ab
Ab → bA       A → aa
Ab → BcD      B → ab
Ac → dc       D → ad

En la gramática anterior, las siguientes cadenas son ejemplos de oraciones: - bAc - Abc - BcDc - bdc

Teniendo en cuenta que se cumplen las siguientes derivaciones: 

S ⇒ Abc ⇒ bAc
S ⇒ Abc
S ⇒ Abc ⇒ BcDc
S ⇒ Abc ⇒ bAc ⇒ bdc

[!note] Definición de oración Dada una gramática G = ($V_N, V_T$, P, S) y una cadena x ∈ $V_T$, se dice que x es una oración* en G si se cumple que S ⇒+ x.

[!example] Ejemplo 4 Sea la gramática del ejemplo 3. En esta gramática son ejemplos de oraciones las siguientes cadenas: - bdc - abaabcad - abbaa

Teniendo en cuenta que se cumple: 

bdc ∈ VT* y S ⇒ Abc ⇒ bAc ⇒ bdc

abaabcad ∈ VT* y S ⇒ Abc ⇒ BcDc ⇒ BAb ⇒ BBcD ⇒ babBcD ⇒ ababcD ⇒ abaabcad

abbaa ∈ VT* y S ⇒ Abc ⇒ BcDc ⇒ BAb ⇒ BbA ⇒ abbA ⇒ abbaa

Observación

Como puede apreciarse, una oración es un caso particular de forma oracional, en la cual todos los símbolos que la componen son símbolos terminales.

[!note] Lenguaje generado por una gramática Dada una gramática G, se llama lenguaje generado por G el conjunto definido del siguiente modo:

$L(G) = {x|x \in V_T^* \text{ y } S \Rightarrow^+ x}$

[!example] Ejemplo 5 Sea la gramática G = ({S, A, B, D}, {a, b, c}, P, S), donde P es el siguiente conjunto de reglas. Si se observan detenidamente, puede verse que la primera de ellas permite efectuar derivaciones de la forma S ⇒+ ABC ... ABCS, donde la subcadena ABC ocurre una o más veces.

S → ABCS      CA → AC
S → ABC       CB → BC
AB → BA       A → a
AC → AC       B → b
BA → AB       C → c
BC → CB

Posteriormente, con la regla S → ABC, se sustituye S y se obtiene una sucesión de dos o más subcadenas ABC. Si en lugar de comenzar con la regla S → ABCS, se aplica inicialmente la segunda regla, se obtiene la subcadena ABC una sola vez. En síntesis, a partir del símbolo de partida, se tiene S ⇒+ ABC ... ABC, donde ABC ocurre al menos una vez.

Después, las seis reglas que siguen a las dos primeras permiten permutar las Aes, Bes y Ces como se desee, mientras que las tres últimas sustituyen estos no terminales por los terminales respectivos.

De todo lo anterior se deduce que el lenguaje generado por la gramática dada es el formado por las cadenas sobre el alfabeto {a, b, c} que contienen la misma cantidad de aes, bes y ces.

[!tip] Equivalencia de gramáticas Dos gramáticas, G₁ y G₂, son equivalentes si L(G₁) = L(G₂).

Las gramáticas pueden ser: - Gramática Regular - Gramática Independiente del Contexto

Definiciones formales finales

Gramática para concatenación de lenguajes

[!note] Definición formal Si tenemos las gramáticas G₁ = (VN₁, VT₁, P₁, S₁) y G₂ = (VN₂, VT₂, P₂, S₂), el lenguaje L(G₁)L(G₂) es generado por la siguiente GIC:

G = (VN₁ ∪ VN₂ ∪ {S}, VT₁ ∪ VT₂, P₁ ∪ P₂ ∪ {S → S₁S₂}, S)

Propiedades importantes sobre las gramáticas

  1. Equivalencia de gramáticas:
  2. Dos gramáticas G₁ y G₂ son equivalentes si y solo si L(G₁) = L(G₂)

  3. Es decir, generan exactamente el mismo lenguaje

  4. Corrección de una gramática G respecto a un lenguaje L:

  5. Se cumple cuando L(G) ⊆ L

  6. Es decir, la gramática no genera palabras que no pertenezcan al lenguaje objetivo

  7. Completitud de una gramática G respecto a un lenguaje L:

  8. Se cumple cuando L ⊆ L(G)

  9. Es decir, la gramática genera al menos todas las palabras del lenguaje objetivo

  10. Gramática bien formada:

  11. Es aquella que es tanto correcta como completa respecto al lenguaje que pretende generar

  12. Es decir, L(G) = L

  13. Gramática Regular

  14. Gramática Independiente del Contexto