Introduction to Grammars

Posted By on April 29, 2016


Download PDF
DFA Minimization
Chomsky Classification of Grammars

Download PDF

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.

Grammar

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

  • N or VN is a set of Non-terminal symbols
  • 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 ⇒ aAb using production S → aAb

⇒ aaAbb using production aA → aAb

⇒ aaaAbbb 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, a2b, ab2, a2b2, ………}

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) = {am bn | m ≥ 0 and n > 0}. We have to find out the grammar G which produces L(G).

Solution

Since L(G) = {am bn | 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) = {am bn | m> 0 and n ≥ 0}. We have to find out the grammar G which produces L(G).

Solution

Since L(G) = {am bn | 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 })

 


Download PDF
DFA Minimization
Chomsky Classification of Grammars

Download PDF

Posted by Akash Kurup

Founder and C.E.O, World4Engineers Educationist and Entrepreneur by passion. Orator and blogger by hobby

Website: http://world4engineers.com