Lenguaje generado por una gramática

Se dice que el conjunto de todas las cadenas que se pueden derivar de una gramática es el lenguaje generado a partir de esa gramática. Un lenguaje generado por una gramáticaG es un subconjunto definido formalmente por

L (G) = {W | W ∈ ∑ *, S ⇒ G W}

Si L(G1) = L(G2), la gramática G1 es equivalente a la gramática G2.

Ejemplo

Si hay una gramática

G: N = {S, A, B} T = {a, b} P = {S → AB, A → a, B → b}

aquí S produce ABy podemos reemplazar A por ay B por b. Aquí, la única cadena aceptada esab, es decir,

L (G) = {ab}

Ejemplo

Supongamos que tenemos la siguiente gramática:

G: N = {S, A, B} T = {a, b} P = {S → AB, A → aA | a, B → bB | b}

El lenguaje generado por esta gramática -

L (G) = {ab, a ² b, ab ² , a ² b ² , ………}

= {a ^m b ⁿ | m ≥ 1 yn ≥ 1}

Construcción de una gramática que genera un lenguaje

Consideraremos algunos idiomas y los convertiremos en una gramática G que produce esos idiomas.

Ejemplo

Problem- Suponga, L (G) = {a ^m b ⁿ | m ≥ 0 yn> 0}. Tenemos que averiguar la gramáticaG que produce L(G).

Solution

Dado que L (G) = {a ^m b ⁿ | m ≥ 0 y n> 0}

el conjunto de cadenas aceptadas se puede reescribir como -

L (G) = {b, ab, bb, aab, abb, …….}

Aquí, el símbolo de inicio debe tomar al menos una 'b' precedida por cualquier número de 'a', incluido el nulo.

Para aceptar el conjunto de cadenas {b, ab, bb, aab, abb, …….}, Hemos tomado las producciones -

S → aS, S → B, B → by B → bB

S → B → b (aceptado)

S → B → bB → bb (aceptado)

S → aS → aB → ab (Aceptado)

S → aS → aaS → aaB → aab (Aceptado)

S → aS → aB → abB → abb (Aceptado)

Por lo tanto, podemos probar que cada cadena en L (G) es aceptada por el lenguaje generado por el conjunto de producción.

De ahí la gramática:

G: ({S, A, B}, {a, b}, S, {S → aS | B, B → b | bB})

Ejemplo

Problem- Suponga, L (G) = {a ^m b ⁿ | m> 0 y n ≥ 0}. Tenemos que averiguar la gramática G que produce L (G).

Solution -

Dado que L (G) = {a ^m b ⁿ | m> 0 y n ≥ 0}, el conjunto de cadenas aceptadas se puede reescribir como -

L (G) = {a, aa, ab, aaa, aab, abb, …….}

Aquí, el símbolo de inicio debe tomar al menos una 'a' seguida de cualquier número de 'b', incluido el nulo.

Para aceptar el conjunto de cadenas {a, aa, ab, aaa, aab, abb, …….}, Hemos tomado las producciones -

S → aA, A → aA, A → B, B → bB, B → λ

S → aA → aB → aλ → a (Aceptado)

S → aA → aaA → aaB → aaλ → aa (Aceptado)

S → aA → aB → abB → abλ → ab (Aceptado)

S → aA → aaA → aaaA → aaaB → aaaλ → aaa (Aceptado)

S → aA → aaA → aaB → aabB → aabλ → aab (Aceptado)

S → aA → aB → abB → abbB → abbλ → abb (Aceptado)

Por lo tanto, podemos probar que cada cadena en L (G) es aceptada por el lenguaje generado por el conjunto de producción.

De ahí la gramática:

G: ({S, A, B}, {a, b}, S, {S → aA, A → aA | B, B → λ | bB})