Definition of Grammar in Automata

G is defined as a quadruple (consisting of four-part) G = {V , T , S , P}.

V: a finite set of objects called variables or non-terminals.

T: a finite set of objects called terminal symbols.

S ∊ V, a special symbol called start variable or non-terminal.

V ∩ T = ɸ  (There no such common symbol between terminals and non-terminals, both are distinct).

P is a finite set of production of form.

The left-hand side of the production can contain variables (non-terminal) and terminals but not empty symbols (λ) and the right-hand side of the production can contain variables and terminals including empty symbols (λ).

The language generated by G is

Strings ω also constructed by non-terminals like ω = ababbba.

ω ∊ T* means strings also belongs to terminals.

It means to start with starting production and after some production rules, we can get a strings ω.

Note: Non-terminal symbols or variable are those symbols which can be replaced multiple times. Terminals symbols are those symbols that cannot be replaced further.

Examples:

G = ({S, A, B}, {a, b}, {S}, {P})

P: S → AB, A → a, B → b

S → AB → aB → ab   (We can generate one string)

From this grammar, we can generate only one string ‘ab’.

So, language generated by this grammar L(G) = {ab}

Important points:

One grammar has one language but one language has several grammars.

Example:

G1 = ({S}, {a, b}, {S}, {P}) is a grammar

P:  S → ab it is also a grammar. Language generated from grammar G1 is L(G) = {ab}

G2 = ({S, A}, {a, b}, {S}, {P})

P:      

S → aA

A → b

Language generated by G2 is L(G) = {ab}

Another grammar:

G3 = ({S, A, B}, {a, b}, {S}, {P})

P: S → AB, A → λ, B → ab  that

Language generated by G3 is L(G) = {ab}

So, here L(G)  = {ab} same but the grammar is different like G, G1, G2, G3.

So, G, G1, G2, G3 all are equivalents.