**1 Answer**

written 2.6 years ago by | • modified 2.6 years ago |

**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
and*Terminals (a, b, c, etc.)*in any combination.*Non-Terminals or variables (A, B, C, S, etc.)* - 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_{0} → S

where S_{0} 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_{0}, creates a new production rule *S _{0} → S*

*Therefore, the grammar will become:*

**S _{0} → 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_{0} → 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_{0} → S

S → ASB | AB

A → aAS | a | aA

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

Also, remove the unit production *S _{0} → S*

*Therefore, its removal from the grammar will produce:*

S_{0} → **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_{0}.

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_{0} → 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_{0} → **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.*

Answer for Define Chomsky Normal Form

5.0k