Classification of Grammar

1. Grammar has set of rules to generate the strings of a language.
2. A grammar G can be formally written as a 4-tuple (N, T, S, P)

Where;

• N or V_N is a set of variables or non-terminal symbols.
• T or ∑ is a set of Terminal symbols.
• S is a special variable called the Start symbol, S ∈ N
• P is Production rules for Terminals and Non-terminals. A production rule has the form α → β, where α and β are strings on V_N ∪ ∑ and least one symbol of α belongs to V_N.

Example:

Grammar : ({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