A context-free grammar is said to be in Chomsky normal form if every
production is of one of these two types:
A → BC (where B and C are Non terminals)
A → σ (where σ is a terminal symbol)
So a CFG in Chomsky normal form has to consist of 2 non- terminals or
one terminal.
Every CFG can be converted into its CNF (Chomsky normal form).
Conversion of a CFG in CNF
To convert this into its equivalent CNF,
S → TU| V
T → a T b | ε
U → c U | ε
V → aVc | W
W → bW | ε
1) First we have to identify the nullable forms, i.e. all the
productions of type A → ε
In this CFG, variable T, U and W are nullable also, V is nullable as
production V → W exists so S will also be nullable as S → V exists. Therefore
all the variables are nullable.
2) Next we have to eliminate all the ε productions, so we have to add
the following productions.
S → T
S → U
T → a b
U → c
V → ac
W → b
After eliminating ε productions, we are left with
S → TU| T | U | V
T → a T b | a b
U → c U | c
V → a V c | ac | W
W → b W | b
3) Identify A - derivable variables for each A. The S-derivable
variables are T, U, V it also includes W as V → W. The V derivable is W.
4) Next eliminate unit productions by adding the following productions.
S → a T b | a b | c U | c | a V c | ac | b W | b
V → b W | b
So now the CFG is
S → TU | a T b | a b | c U | c | a V c | ac | b W | b
T → a T b | a b
U → c U | c
V → a V c | ac | b W | b
W → b W | b
5) Next for converting to CNF, we have to replace all the terminals with
non terminals A, B, C for terminals a, b, c respectively, in productions whose
right sides are not single terminals.
S → TU | A T B | AB | CU | c | AVC | AC | BW | b
T → A T B | AB
U → CU | c
V → AVC | AC | BW | b
W → B W | b
Now the grammar is not in CNF because of the productions where there are
3 non terminals on the right side. So we replace them as follows and the final
CNF after the replacements will be:
S → TU | A X | AB | CU | c | A Y | AC | BW | b
X → TB
Y → VC
T → AZ | AB
Z → TB
U → CU | c
V → AP | AC | BW | b
P → VC
W → BW | b
Now, X and Z both are same, so one of them can be eliminated and also Y
and P are identical so again one of them can be eliminated.
Another simpler example can be,
The CFG for an bn is,
S → a S b | ab
Converting it to CNF we get,
S → AS1 | AB
S1→ SB
A → a
B → b
Recommended articles:
Comments
Post a Comment