Introduction to Grammars in Theory of Computation

In this article, we are going to learn about the introduction of grammars in theory of computation (TOC).
Submitted by Mahak Jain, on November 14, 2018

Noam Chomsky gave a mathematical model of grammar. This model is used to write computer languages effectively.

A grammar can be represented as a 4 tuple:

(N, T, P, S)

N denotes the set of variables or non-terminal symbols.
T denotes the set of terminal symbols.
S is a special variable called start symbol and S belongs to N.
P is production rules for terminals and non-terminals α → β, where α and β are strings on VN ∪ ∑ and least one symbol of α belongs to VN.

Example:

Grammar G1 − ({S, C, D}, {c, d}, S, {S → CD, C → c, D → d})

Here,

S, C, and D Are Non-terminal symbols;
c and d are Terminal symbols
S is the Start symbol, S belongs to N
Productions, P: S → CD, C → c, D → d

Example:

Grammar G2 − (({S, C}, {c,d}, S,{S → cCd, cC → ccCd, C → ε } )

Here,

S and C Are Non-terminal symbols.
c and d are Terminal symbols.
ε is an empty string.
S is the Start symbol, S belongs to N
Production P : S → cCd, cC → ccCd, C → ε

Derivations

If a grammar G has a production α → β, it denotes that x α y derives x β y in G. This derivation can be represented as: x α y ⇒ G x β y

Example:

Let grammar be − G = ({S, C}, {c, b}, S, {S →cCd, cC → ccCd, C → ε } )

Derived strings:

S ⇒ cCd using production S →cCd
⇒ccCdd using production cC →cCd
⇒cccCddd using production cC→ cCd
⇒cccddd using production C→ ε

Language

It is The set of all strings a grammar can derive. It is said to be generated by that grammar.

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

If L(G1) = L(G2), the Grammar G1 and Grammar G2 are equivalent.

Example:

Let grammar be: G: N = {S, C, D} T = {c, d} P = {S → CD, C → c, D → d}

Here, S produces CD, and we can replace C by c, and C by d. Here, the only accepted string is cd, i.e., L(G) = {cd}

Example:

Suppose we have the following grammar: G: N = {S, C, D} T = {c,d} P = {S → CD, C → cC|c, D → dD|d}

The language generated by this grammar

L(G) = {cd, c2d, cd2, c2d2, ...}
= {cm dn | m ≥ 1 and n ≥ 1}

Now, We'll consider some given languages and then convert it into a grammar G which is responsible for production of those languages.

Example:

Suppose, L (G) = {cm dn | m ≥ 0 and n > 0}.

Solution:

Since L(G) = {cm dn | m ≥ 0 and n > 0}

The set of strings accepted are: L(G) = {d, cd,cc, ccd, cdd, ...}

To accept this string set {d, cd, cc, ccd, cdd, ...}

We will consider the productions

    S → cS , S → D, D → d and D → dD
    S → D → d (Accepted)
    S → D → dD → dd (Accepted)
    S → cS → cD → cd (Accepted)
    S → cS → ccS → ccD → ccd(Accepted)
    S → cS → cD → cdD → cdd (Accepted)