Where e is null.

Context-Free Grammar (CFG)

• A Context-Free Grammar (CFG) is one form of grammar that is used to generate all possible patterns of strings in a given formal language.
• In CFG at the Right Hand Side (RHS) of production, there may be any number of Terminals (a, b, c, etc.) and Non-Terminals or variables (A, B, C, S, etc.) in any combination.
• So need to normalize such grammar in some specific format.
• There should be a fixed number of terminals and non-terminals, in CFG with some conditions.
• Based on this there are two normal forms are classified as follows:
  • Chomsky Normal Form (CNF)
  • Greibach Normal Form (GNF)
• These normal forms have nice combinatorial structures which are useful in proving the properties of CFLs.
• Here we see Chomsky Normal Form (CNF) in detail.

Chomsky Normal Form (CNF)

• A CFG is said to be in Chomsky Normal Form (in short, CNF) if the following conditions are true.

Condition 1 - A non-terminal (variable) generating two non-terminals.

For example, A → BC

Condition 2 - A non-terminal (variable) generating a terminal.

For example, A → a

Condition 3 - Start symbol generating ε.

For example, S → ε

Condition 4 - The start variable is not present on the Right Hand Side (RHS) of any rule.

Steps for converting CFG into CNF

Step 1 - Eliminate the start symbol from RHS.

If start symbol S is at the RHS of any production in the grammar, then create a new production as: S₀ → S

where S₀ is the new start symbol.

Step 2 - Eliminate null, unit, and useless productions.

If CFG contains null, unit, or useless production rules, eliminate them. (CFG Simplification Stage)

Step 3 - Eliminate terminals from RHS if they exist with other terminals or non-terminals.

Example – S → aA

can be decomposed as follows:

S → RA

R → a

Finally, it is equal to S → aA only.

Step 4 − Eliminate the RHS with more than two non-terminals.

Example – S → ABS

can be decomposed as follows:

S → RS

R → AB

Finally, it is equal to S → ABS only.

This indicates, in the CNF number and nature of the symbols on the RHS are strictly fixed and restricted to a specific limit.

The Given Grammar

Let’s solve the given example of grammar

S → ASB | ε

A → aAS | a

B →SbS | A | bb

• We will convert the above grammar into the CNF.
• The rules/variables that get added at each step are shown in bold font.

Step 1 –

As start symbol S appears on the RHS rule A & B.

Hence, adding a new start variable S₀, creates a new production rule S₀ → S

Therefore, the grammar will become:

S₀ → S

S → ASB | ε

A → aAS | a

B →SbS | A | bb

Step 2 –

As grammar contains Null production S → ε

Therefore, its removal from the grammar will produce:

S₀ → S

S → ASB | AB

A → aAS | a | aA

B →SbS | A | bb | bS | Sb | b

As grammar contains Unit production B → A

Therefore, its removal from the grammar will produce:

S₀ → S

S → ASB | AB

A → aAS | a | aA

B → SbS | aAS | a | aA | bb | bS | Sb | b

Also, remove the unit production S₀ → S

Therefore, its removal from the grammar will produce:

S₀ → ASB | AB

S → ASB | AB

A → aAS | a | aA

B → SbS | aAS | a | aA | bb | bS | Sb | b

Now, we can see that A and B each derive terminal strings, and therefore so does S₀.

Thus, there are no useless symbols.

The CFG is now simplified completely and now moves towards the next step.

Step 3 –

Adding variables and productions U → a and V → b, where all strings that are not with a single terminal.

Therefore, the grammar will become:

S₀ → ASB | AB

S → ASB | AB

A → UAS | a | UA

B → SVS | UAS | a | UA | VV | VS | SV | b

U → a

V → b

Finally, adding new variables P and Q and productions P → AS and Q → SV, where all strings of terminals of length 3.

Therefore, the grammar will become:

S₀ → PB | AB

S → PB | AB

A → UP | a | UA

B → QS | UP | a | UA | VV | VS | SV | b

P → AS

Q → SV

U → a

V → b

So this is the required CNF for a given grammar.