I am working with grammars that need to be in Greibach Normal Form. I want to check whether a grammar recognises a string. In order to perform CYK the grammar would have to be converted into CNF. Is there an established way of carrying out such conversion?
You can just apply the usual procedure that converts any context-free grammar (CFG) to Chomsky normal form (CNF), since a CFG in Greibach normal form (GNF) is still a CFG.
In the case of GNF, the task is, in fact, easier. All you need is to apply the following two rules repeatedly, as described by Wikipedia, until there is no nonsolitary terminals nor more than 2 nonterminals on the right-hand sides of the production rules.
- Eliminate rules with nonsolitary terminals. In the case of GNF, this is used to eliminate the first terminals in the production rules.
- Eliminate right-hand sides with more than 2 nonterminals.