Context Free Grammar

A grammar is said to be context-free, if every production is in the form -

A → α

where, A is non-terminal symbol and α ∈ (N ∪ ∑)*. The set of production rules describes all possible strings. In this, productions are simple replacements.

Production rules

In context-free grammar, all rules are one to one, one-to-many or one-to-none. The left hand side of the production rule is always a non-terminal symbol.

Formal definition of Context-free Grammar

A context-free grammar is 4 tuple -

G = (V, Σ, P, S)

V - a finite set of non-terminal symbols,
Σ - set of terminal symbols,
P - a finite set of productions or rules,
S - a start symbol.

The production rule of context-free grammar -

A → α

The above rule replaces A with α.

A → α
A → β

The above rule replaces A with α or β.

T → AA

In the above, first we replace A with β and second A with α and get -

T -> βα

A language L is said to be context-free if L = L(G) and G is context-free grammar. A context-free language can be recognized by Push-Down Automata (PDA).