Linguaggio generato da una grammatica

Si dice che l'insieme di tutte le stringhe che possono essere derivate da una grammatica sia il linguaggio generato da quella grammatica. Una lingua generata da una grammaticaG è un sottoinsieme definito formalmente da

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

Se L(G1) = L(G2), la grammatica G1 è equivalente alla grammatica G2.

Esempio

Se c'è una grammatica

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

Qui S produce ABe possiamo sostituire A di a, e B di b. Qui, l'unica stringa accettata èab, cioè

L (G) = {ab}

Esempio

Supponiamo di avere la seguente grammatica:

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

La lingua generata da questa grammatica -

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

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

Costruzione di una grammatica che genera una lingua

Considereremo alcune lingue e le convertiremo in una grammatica G che produce quelle lingue.

Esempio

Problem- Supponiamo che L (G) = {a ^m b ⁿ | m ≥ 0 e n> 0}. Dobbiamo scoprire la grammaticaG che produce L(G).

Solution

Poiché L (G) = {a ^m b ⁿ | m ≥ 0 e n> 0}

l'insieme di stringhe accettate può essere riscritto come -

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

Qui, il simbolo di inizio deve prendere almeno una "b" preceduta da un numero qualsiasi di "a" incluso null.

Per accettare l'insieme di stringhe {b, ab, bb, aab, abb, …….}, Abbiamo preso le produzioni -

S → aS, S → B, B → be B → bB

S → B → b (Accettato)

S → B → bB → bb (Accettato)

S → aS → aB → ab (Accettato)

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

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

Quindi, possiamo provare che ogni singola stringa in L (G) è accettata dal linguaggio generato dall'insieme di produzione.

Da qui la grammatica -

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

Esempio

Problem- Supponiamo che L (G) = {a ^m b ⁿ | m> 0 e n ≥ 0}. Dobbiamo scoprire la grammatica G che produce L (G).

Solution -

Poiché L (G) = {a ^m b ⁿ | m> 0 en ≥ 0}, l'insieme di stringhe accettate può essere riscritto come -

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

Qui, il simbolo di inizio deve prendere almeno una "a" seguita da un numero qualsiasi di "b" incluso null.

Per accettare l'insieme di stringhe {a, aa, ab, aaa, aab, abb, …….}, Abbiamo preso le produzioni -

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

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

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

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

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

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

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

Quindi, possiamo provare che ogni singola stringa in L (G) è accettata dal linguaggio generato dall'insieme di produzione.

Da qui la grammatica -

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