# Introduction to Grammars

In the literary sense of the term, grammars denote syntactical rules for conversation in natural languages. Linguistics have attempted to define grammars since the inception of natural languages like English, Sanskrit, Mandarin, etc. The theory of formal languages finds its applicability extensively in the fields of Computer Science. **Noam Chomsky** gave a mathematical model of grammar in 1956 which is effective for writing computer languages.

Contents

Contents

## Grammar

A grammar **G** can be formally written as a 4-tuple (N, T, S, P) where

**N**or**V**is a set of Non-terminal symbols_{N}**T**or**∑**is a set of Terminal symbols**S**is the Start symbol, S ∈ N**P**is Production rules for Terminals and Non-terminals

### Example

Grammar G1 −

({S, A, B}, {a, b}, S, {S → AB, A → a, B → b})

Here,

**S, A,** and **B** are Non-terminal symbols;

**a** and **b** are Terminal symbols

**S** is the Start symbol, S ∈ N

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

### Example

Grammar G2 −

({S, A}, {a, b}, S,{S → aAb, aA →aaAb, A → ε } )

Here,

**S**and**A**are Non-terminal symbols.**a**and**b**are Terminal symbols.**ε**is an empty string.**S**is the Start symbol, S ∈ N- Production
**P : S → aAb, aA → aaAb, A → ε**

## Derivations from a Grammar

Strings may be derived from other strings using the productions in a grammar. If a grammar **G** has a production **α → β,** we can say that **x α y** derives **x β y** in **G**. This derivation is written as −

**x α y ⇒G x β y**

### Example

Let us consider the grammar −

G2 = ({S, A}, {a, b}, S, {S → aAb, aA → aaAb, A → ε } )

Some of the strings that can be derived are −

S ⇒ __aA__b using production S → aAb

⇒ a__aA__bb using production aA → aAb

⇒ aaa__A__bbb using production aA → aAb

⇒ aaabbb using production A → ε

The set of all strings that can be derived from a grammar is said to be the language generated from that grammar. A language generated by a grammar **G** is a subset formally defined by

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

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

### Example

If there is a grammar

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

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

L(G) = {ab}

### Example

Suppose we have the following grammar −trailer movie Sherlock: The Final Problem

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

The language generated by this grammar −

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

## Construction of a Grammar Generating a Language

We’ll consider some languages and convert it into a grammar G which produces those languages.

### Example

**Problem** − Suppose, L (G) = {a^{m} b^{n} | m ≥ 0 and n > 0}. We have to find out the grammar **G** which produces **L(G)**.

**Solution**

Since L(G) = {a^{m} b^{n} | m ≥ 0 and n > 0}

the set of strings accepted can be rewritten 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 accept the 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)

Thus, we can prove 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 → aS | B, B → b | bB })

### Example

**Problem** − Suppose, L (G) = {a^{m} b^{n} | m> 0 and n ≥ 0}. We have to find out the grammar G which produces L(G).

**Solution** −

Since L(G) = {a^{m} b^{n} | m> 0 and n ≥ 0}, the set of strings accepted can be rewritten as −

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

Here, the start symbol has to take at least 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)

Thus, we can prove 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 })