Langage généré par une grammaire

L'ensemble de toutes les chaînes qui peuvent être dérivées d'une grammaire est dit être le langage généré à partir de cette grammaire. Un langage généré par une grammaireG est un sous-ensemble formellement défini par

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

Si L(G1) = L(G2), la grammaire G1 équivaut à la grammaire G2.

Exemple

S'il y a une grammaire

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

Ici S produit AB, et nous pouvons remplacer A par a, et B par b. Ici, la seule chaîne acceptée estab, c'est à dire,

L (G) = {ab}

Exemple

Supposons que nous ayons la grammaire suivante -

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

Le langage généré par cette grammaire -

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

= {a m b n | m ≥ 1 et n ≥ 1}

Construction d'une grammaire générant un langage

Nous examinerons certaines langues et les convertirons en une grammaire G qui produit ces langues.

Exemple

Problem- Supposons que L (G) = {a m b n | m ≥ 0 et n> 0}. Nous devons découvrir la grammaireG qui produit L(G).

Solution

Puisque L (G) = {a m b n | m ≥ 0 et n> 0}

l'ensemble de chaînes acceptées peut être réécrit comme -

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

Ici, le symbole de départ doit prendre au moins un «b» précédé d'un nombre quelconque de «a», y compris nul.

Pour accepter l'ensemble de chaînes {b, ab, bb, aab, abb, …….}, Nous avons pris les productions -

S → aS, S → B, B → b et B → bB

S → B → b (accepté)

S → B → bB → bb (accepté)

S → aS → aB → ab (Accepté)

S → aS → aaS → aaB → aab (Accepté)

S → aS → aB → abB → abb (Accepté)

Ainsi, nous pouvons prouver que chaque chaîne de L (G) est acceptée par le langage généré par l'ensemble de production.

D'où la grammaire -

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

Exemple

Problem- Supposons que L (G) = {a m b n | m> 0 et n ≥ 0}. Nous devons trouver la grammaire G qui produit L (G).

Solution -

Puisque L (G) = {a m b n | m> 0 et n ≥ 0}, l'ensemble des chaînes acceptées peut être réécrit comme -

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

Ici, le symbole de départ doit prendre au moins un «a» suivi d'un nombre quelconque de «b», y compris nul.

Pour accepter l'ensemble de chaînes {a, aa, ab, aaa, aab, abb, …….}, Nous avons pris les productions -

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

S → aA → aB → aλ → a (Accepté)

S → aA → aaA → aaB → aaλ → aa (Accepté)

S → aA → aB → abB → abλ → ab (Accepté)

S → aA → aaA → aaaA → aaaB → aaaλ → aaa (Accepté)

S → aA → aaA → aaB → aabB → aabλ → aab (Accepté)

S → aA → aB → abB → abbB → abbλ → abb (Accepté)

Ainsi, nous pouvons prouver que chaque chaîne de L (G) est acceptée par le langage généré par l'ensemble de production.

D'où la grammaire -

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