# 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).

Context Sensitive Grammar

Regular Grammar