Linguagem gerada por uma gramática

O conjunto de todas as strings que podem ser derivadas de uma gramática é considerado a linguagem gerada por essa gramática. Uma linguagem gerada por uma gramáticaG é um subconjunto formalmente definido por

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

E se L(G1) = L(G2), a gramática G1 é equivalente à gramática G2.

Exemplo

Se houver uma gramática

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

Aqui S produz AB, e podemos substituir A por a, e B por b. Aqui, a única string aceita éab, ou seja,

L (G) = {ab}

Exemplo

Suponha que temos a seguinte gramática -

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

A linguagem gerada por esta gramática -

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

= {a ^m b ⁿ | m ≥ 1 e n ≥ 1}

Construção de uma gramática gerando uma linguagem

Vamos considerar algumas línguas e convertê-las em uma gramática G que produz essas línguas.

Exemplo

Problem- Suponha, L (G) = {a ^m b ⁿ | m ≥ 0 e n> 0}. Temos que descobrir a gramáticaG que produz L(G).

Solution

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

o conjunto de strings aceito pode ser reescrito como -

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

Aqui, o símbolo de início deve ter pelo menos um 'b' precedido por qualquer número de 'a' incluindo nulo.

Para aceitar o conjunto de strings {b, ab, bb, aab, abb, …….}, Pegamos as produções -

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

S → B → b (aceito)

S → B → bB → bb (aceito)

S → aS → aB → ab (aceito)

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

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

Assim, podemos provar que cada string em L (G) é aceita pela linguagem gerada pelo conjunto de produção.

Daí a gramática -

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

Exemplo

Problem- Suponha, L (G) = {a ^m b ⁿ | m> 0 e n ≥ 0}. Temos que descobrir a gramática G que produz L (G).

Solution -

Como L (G) = {a ^m b ⁿ | m> 0 e n ≥ 0}, o conjunto de strings aceito pode ser reescrito como -

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

Aqui, o símbolo de início deve ter pelo menos um 'a' seguido por qualquer número de 'b' incluindo nulo.

Para aceitar o conjunto de strings {a, aa, ab, aaa, aab, abb, …….}, Pegamos as produções -

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

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

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

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

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

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

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

Assim, podemos provar que cada string em L (G) é aceita pela linguagem gerada pelo conjunto de produção.

Daí a gramática -

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