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.