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 the important Chomsky normal form (CNF) and the 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 CYKS 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”. Simplifications are typically the first step in converting a grammar to some normal form such as Chomsky normal form or Greibach normal form. I introduce these ideas at a high-level in the next video.
The process of simplifying a grammar consists of three fundamental steps:
- Removing nullable variables
- Removing unit productions
- Removing useless productions. This last step is done into two subparts:
- Removing non-generating variables
- Removing unreachable variables
I discuss each of these steps in detail.
Removing nullable variables
Removing unit productions
Removing useless productions
Extremely important note: In the next video, I discuss useless productions in the wrong order. Useless productions should always be removed by first removing non-generating variables and then unreachable variables. Why? Because removing non-generating variables may introduce unreachbility. Please keep this in mind for the exercises below.
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 discuss in more detail the Chomsky normal form (CNF). I show how any context-free grammar can converted to an equivalent grammar in CNF.