1
$\begingroup$

A CFG is in strong GNF when all rewrite rules are in the following form:

$A \rightarrow aA_1...A_n$

where $n \leq 2$.

$\endgroup$
  • 1
    $\begingroup$ What are your thoughts? Have you tried coming up with such an algorithm? Have you tried searching the net for such an algorithm? $\endgroup$ – Yuval Filmus Nov 27 '16 at 8:33
  • $\begingroup$ I had already constructed the algorithm for converting a CNF CFG into a GNF CFG. From there I thought it'd be easier to convert a GNF CFG into a SGNF CFG but I have yet to find a way. I had looked around but it appears strong GNF is not a widely used term. $\endgroup$ – user393454 Nov 27 '16 at 8:51
1
$\begingroup$

Such an algorithm is described in Koch and Blum, Greibach Normal Form Transformation, Revisited.

| 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.