# Normal Forms of CFGs

This section will be about context-free grammar simplification and normal forms. I will present all the steps necessary to simplify a grammar. I will then discuss two important normal forms of context-free grammars: Chomsky normal form (CNF) and Greibach normal form (GNF). I will show how you can convert any context-free grammar into an equivalent grammar in CNF. The simplification of CFGs and the conversion of a CFG to CNF are slightly tedious processes. Nonetheless, they are crucial because they convert grammars into a form that can be accepted by *a very important algorithm* which we will discuss in the next section. Sneak peak, I am talking about the CYK algorithm. You can find the notes related to this section here.

### Grammar simplification

The simplification of a context-free grammar \(G\) involves converting its production rules so that they have a consistent form. The term simplification is somewhat misleading because, as you will see, grammar simplification algorithms can cause an initial grammar \(G\) to become, in some sense, â€śmore messyâ€ť.

The process of simplifying a grammar consists of three fundamental steps:

- Removing \(\lambda\)-productions and nullable variables
- Removing unit productions
- Removing useless productions

I discuss each of these steps in detail.

#### Removing \(lambda\)-productions and nullable variables

`Video on the way! Refer to slides for now.`

#### Removing unit productions

`Video on the way! Refer to slides for now.`

#### Removing useless productions

`Video on the way! Refer to slides for now.`

### Normal forms

Now that we know how to simplify context-free grammars, we will discuss their conversion to normal forms. Normal forms are everywhere in mathematics: Orthonormal vectors, normal matrices, etc. In general, a normal form simply restricts a mathematical object to respect a certain structure. This typically allows theorems and results to be stated much more cleanly, without having to deal with additional edge cases. In our case, context-free grammar normal forms will be useful as they will allow us to create simple parsing algorithms, algorithms which check whether \(w \in L(G)\).

In the next video I introduce two normal forms: Chomsky Normal Forma and Greibach Normal Form. I show how any context-free grammar can converted to an equivalent grammar in CNF. I leave the details of the algorithm for GNF as an exercise.

`Video on the way! Refer to slides for now.`

### Exercises

**Exercise.**Show that any CFG \(G\) such that \(\lambda \notin L(G)\) can be converted to Greibach Normal Form.

**Exercise.**Provide a procedure that converts any CFG \(G\) such that \(\lambda \notin L(G)\) into Greibach Normal Form.