can anyone let me know if there is any software to convert Chomsky normal form to Backus–Naur Form and vice versa?
3 Answers
2
votes
Well, Chomsky Normal Form and Backus-Naur Form aren't really the same kind of concept, so I don't really think so. But if you told us what you needed this software for we might be able to help.
Now, going from what you asked, I'm assuming you want some kind of code to normalize a BNF grammar to Chomsky Normal Form. As far as I know, no such software exists, but it's possible some exists, assuming that it's a task that's actually computationally feasible.
But, if you can be more concrete about what you actually need we'll be able to give you useful advice about that task.
EDIT: After digging a bit in my books, it turns out that it's entriely possible to formulate an algorithm to convert an arbitrary CFG to Chomsky Normal Form. I don't have the actual algorithm or its complexity though.
2
votes
Maybe JFLAP will do what you're looking for.
I've not used it yet myself, but it was recommended to me by my Automata professor.
Looking on the "What is JFLAP?" page, it appears that it can convert from "CFG -> CNF" which sounds like what you're looking to do.
1
votes
As was pointed out, my original answer that BNF is already in CNF was wrong. You can convert any context-free grammar to CNF as explained here (PDF). The conversion process is also illustrated in Sipser 2nd Ed. pages 106-109 if you have access to it. I don't know if there's existing software that automates this process (but it would seem simple to write).
