The dynamic programming algorithm requires the context-free grammar to be rendered into Chomsky normal form (CNF), because it tests for possibilities to split the current sequence in half. Any context-free grammar that does not generate the empty string can be represented in CNF using only production rules of the forms A → α {\displaystyle A\rightarrow \alpha } and A → B C {\displaystyle A\rightarrow BC} .