Language Generated by a Grammar - Automata Theory

How can a Language Generated by a Grammar?

The set of all strings which can be generated from a grammar is called as the language generated from that grammar. Usually a language created by a grammar G is also called as a subset which is defined by

language

If L(G1) = L(G2), the Grammar G1 is similar to the Grammar G2.

Example

While if there is a grammar

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

Here S creates AB, and you can replace A by a, and B by b. Here, the only accepted string is ab, i.e.,

L(G) = {ab}

Example

Let’s assume that if we have the following grammar −

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

The language generated by this grammar −

language

Construction of a Grammar Generating a Language

Let’s take some languages and change then into a grammar G which delivers those languages.

Example

Problem − Suppose, lanaguge. Let’s find out the grammar G which produces L(G).

Solution

Since langauge

You can rewrite the set of strings accepted as −

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

Here, the start symbol has to take at least one ‘b’ preceded by any number of ‘a’ including null.

To make acceptance of a string set {b, ab, bb, aab, abb, …….}, we have taken the productions −

S → aS , S → B, B → b and B → bB

S → B → b (Accepted)

S → B → bB → bb (Accepted)

S → aS → aB → ab (Accepted)

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

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

So we can prove that every single string in L(G) is accepted by the language created by the production set.

Hence the grammar −

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

Example

Problem – If lnagauge. Let’s find out the grammar G which produces L(G).

Solution −

Sincesolu you can rewrite the set of strings can be rewritten as −

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

The start symbol has to include atleast one ‘a’ followed by any number of ‘b’ including null.

To accept the string set {a, aa, ab, aaa, aab, abb, …….}, we have taken the productions −

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

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

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

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

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

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

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

So we can prove that every single string in L(G) is accepted by the language generated by the production set.

Hence the grammar −

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

Automata Theory Related Tutorials

Automata Theory Related Practice Tests

All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

Automata Theory Topics