The Backus-Naur Form is a compact way to describe a

context-free grammar.If you have a context-free grammar G=(N,T,P,o), where N is the not empty, finite set of

non-terminal symbols, T is the not

empty,

finite set of

terminal symbols, P is the

finite set of

derivation rules and o is ∈ N is the start symbol.

Example:

T = {a,b}, N = {a}, P = { o → aob, o → ε}

This grammar describes the following language: L(G)={a^n b^n | n ≥ 0}

Now let's come to the Backus-Naur Form. In this form there are several derivation rules summed up to one rule.

The rules for reducing the rules are:

A → b1, A → b2, ..., A → bn can be reduced to A → b1|b2|...|bn

A → ac, A → abc can be reduced to A → a[b]c

A → ac, A → aBc, B → b, B → Bb can be reduced to A → a{b}c (this simply means 0,1 or more bs)

Example:
The example above is not useful for this. It would stay unchanged. So lets create a new example:

T={a,b,c,d}, N = {A,B,C,D}, P = {o → ABC, A → a, A → c, B → abc, B → ac, C → bDd, C → bd, D → a, D → Da}

The both A rules can be reduced to A → a|c

The both B rules can be reduced to B → a[b]c

The C and D rules can be reduced to C → b{a}d

Then P' = {o → ABC, A → a|c, B → a[b]c, C → b{a}d }