>

The general form of a grammar is G =(N,T,P,S).

N = finite set of non terminal

T = finite set of terminals

P = Production rules

S = Start state

The language generated by the grammar will be of the form

L(G) ={w | w ∈ T*, S*=>w}

If you have any doubts about the above mentioned things please go through the links below.

http://www.martinjacob.info/2012/05/12/grammar-in-a-language-context-free-phrase-structure-type-012-3/

http://www.martinjacob.info/2012/05/12/parsing-production-rules-derivation/

In this post we shall see how languages are derived from a given grammar. The point to be noted here is that all the terminal strings derivable from the grammar belong to the language.

Ex. 1

N={S} (the only non terminal is the start symbol)

T={a,b}(a and b are the terminal symbols)

P={1. S → aSb

2. S → ab} {1 and 2 are the set of production rules )

The above specified grammar is type 2 grammar because it has only one non terminal S on the LHS and has string on the RHS.

Now we shall derive the language generated .

Using the second production rule :

S => ab

Using the first rule first and then the second rule :

S => aSb

S => aabb

ie a^2 b^2

Using the first rule two times and then the second rule

S => aSb

S => aaSbb

S => aaabbb

ie a^3 b^3

The parse tree for a^3 b^3 is given below. To find the language generated we read the leafs of the tree from the left to the right.

 Ab,a^2 b^2 and a^3 b^3 here we can see a pattern being developed. When ever an ‘a’ is added on the LHS of the result a corresponding ‘b’ is added on the RHS. So the language generated will be of the form

L(G)= (a^nb^n | n>=1)

In this language the rule 1 will be applied n-1 times and rule 2 once.

Ex.2

Consider the grammar

N = {S}

T = {a,b,c}

P = { 1 .S → aSa

2. S → bSb

3. S → C }

Lets find out the language generated by this grammar

Using the third production rule

S => c

Therefore c belong to the language L(G).

Using the first production rule first and the third production rule second

S => aSa

=> aca

Therefore aca belongs to the language L(G)

Using the second production rule first and the third production rule second

S => bSb

=> bcb

Therefore bcb belongs to the language L(G)

Using the first production rule first, second production rule second and the third production rule last.

S => aSa

=> abSba

=> abcba

Therefore abcba belongs to the language L(G)

The parse tree is like this

In this language the pattern we can identify is that the string after the ‘c’ will be the reversed form of the string before c . ab c ba here string before c is ab and string after c is ba.

The general representation of the language is generated by this grammar is

L(G) = {w c w(r) | w ∈(a,b) }