Context-Free Grammar (CFG) and Languages

Context-Free Grammar (CFG) and Languages

Definition :

The context free grammar can be formally defined as a set denoted by G = (V, T, P, S) where V and T are set of non-terminals and terminals respectively. P is set of production rules, where each production rule is in the form of

non-terminal → non-terminals

or non-terminal → terminals

S is a start symbol.

For example,

P = {S→ S + S

S→ S * S

S→ (S)

S→ 4}

If the language is 4 + 4 * 4 then we can use the production rules given by P. The start symbol is S. The number of non-terminals in the rules P is one and the only non terminal i.e. S. The terminals are +, *, (,) and 4.

We are using following conventions.

1. The capital letters are used to denote the non-terminals.

2. The lower case letters are used to denote the terminals.

Example: The formation of production rules for checking syntax of any English statement is

SENTENCE → NOUN VERB

NOUN→ Rama / Seeta / Gopal

VERB→ goes / writes / sings