Kleeneliness is next to Gödeliness

Chomsky Normal Form

All productions are of the form $A \to BC$ or $A \to \sigma$ (where $\sigma \in T$ and $A, B, C \in N$).

Knowing them is important for various reasons; for instance, they are used in the proof of correctness of the Pumping Lemma for CF languages.

Greibach Normal Form

All productions are of the form $A \to \sigma B_1 \dots B_n$ (where $\sigma \in T$ and $A, B_1, \dots, B_n \in N$, $n \ge 0$).

One of the reasons to know them is that they are used in algorithms to switch from a CFG to a Pushdown Automaton (PDA).

If you want to learn about Noam Chomsky and Sheila Greibach, you can go to:

Revision: 2026-04-25