1
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.