GRAMMAR IN THEORY OF COMPUTATION

->Grammar is used as standard way to representing a language.

->It is used to check whether the given particular string is a part of the given language with some conditions, or not.

->It is a finite set of formal rules for generating syntactically correct sentences or meaningful correct sentences. 

->Grammar is basically composed of two basic elements –

Terminal Symbols –

Terminal symbols are those which are the components of the sentences generated using a grammar and are represented using small case letter like a, b, c etc.

Non-Terminal Symbols –
Non-Terminal Symbols are those symbols which take part in the generation of the sentence but are not the component of the sentence. Non-Terminal Symbols are also called Auxiliary Symbols and Variables. These symbols are represented using a capital letter like A, B, C, etc.

->A grammar is defined as quadruple i.e. 

EXAMPLE:- 

S-->aSb/ε

-Here 'S' is the start symbol, 'a' & 'b' are terminals and epsilon is a null production.

-By analyzing this grammar rule we have to make a string of any length which contains 'a' and 'b' as start symbol and end symbol

-minimum length will be find out by placing epsilon production at the place of 'S' in right hand side.

i.e. S=aεb (epsilon means null)

we gain minimum length = ab

-now we can find more strings by replacing 'S' with its own production rule.

i.e. S=a aSb b

now by again putting epsilon in place of 'S' we get string 'aabb'.

-continuing or repeating this rule again and again like replacing 'S' with its own production rule 2-times or 3-times or many times i.e. S=a a aSb b b  or  S=a a a aSb b b b and so on...

we get many more strings of any length after putting epsilon in place of S at last step.

like S={ab, aaabbb, aaaabbbb, .......}

-In general for this particular example, it generates a string of type (a^n b^n).

EXAMPLE:-

Let's take an example having multiple production rule for constructing a string

S--> SS

S--> aSb

S--> bSa

S--> ε

-In above we have multiple set of production rules so we have to deal with each other.

Let's have look on some cases for producing a string.

-First in one production rule having S--> SS, replace S by any below production rules i.e. either with 'aSb' or with 'bSa' 

S--> aSb bSa

Now you can put epsilon in place of 'S' then we get string 'abba'.

-Now if you replace S by with same production rule i.e.

S--> aSbaSb or S--> bSabSa

after then replacing S with epsilon we get strings 'abab' and 'baba'.

-Another way is replacing miscellaneously i.e

S--> aSb bSa  ->  S--> a aSb b b aSb a

and after replacing S by epsilon we get string 'aabbbaba'.

...And there are many more cases to forms many strings of any length.