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})