Grammar in Theory of Computing

Grammar is a set of rules and regulations for constructing a language. Grammar defines how strings are generated in a language.

In TOC, a Grammar is represented by four tuples.

G = { V_NT, V_T, P, S }

V_NT : Finite set of Non-terminal symbols

V_T : Finite set of terminal symbols

P : Set of Production Rules

S : Start symbol . It is the symbol from where strings are produced ). It is a subset of V_NT .

Terminal Symbols are represented by small case letters. (a,b,c…)

Non Terminal Symbols are represented by capital letters. (A,B,C…). These symbols take part in language generation but are not a part of it.

Production Rules – used to generate new sequences of strings and symbols. It is denoted in LHS to RHS pattern.
x -> y, where x can be a set of non terminal symbols or a set of terminal symbol or combination of both and cannot be null. y can be a set of non-terminal symbols or a set of terminal symbols or combination of both and can be null. 

Example 1.  G = { |S|, |a|, | P: S->a,S->aS| , S }

In the above example, S is the non-terminal symbol and a is the terminal symbol. The production rules are 1) S->a , 2) S->aS. S is the start symbol and is a subset of V_NT. So , we start generating the language by the start symbol.

S

S->a   [ using production rule 1 ]

OR

S->aS   [ using production rule 2 ]

S->aaS  [ using production rule 2 ]

S->aaaS  [ using production rule 2 ]

S->aaaaS  [ using production rule 2 ]

In this situation , a can be replaced n number of times using production rule 2. Therefore , we can write the language that will be generated like ; L(G) = { aⁿ | n>=1 }, which also means that this grammar can be used to generate strings of the form (a)⁺ which defines the Positive Closure property.