hi..can anyone let me know if there is any software to convert Chomsky normal form to Backus–Naur Form and vice versa?
+1
A:
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).
Bill the Lizard
2009-03-09 00:54:41
I'm sorry, but that's wrong. BNF is a notation for general CFGs so your statement is the same as saying "all CFGs are on Chomsky Normal Form". The crux here is that Chomsky Normal Form requires all nonterminal productions to have only two nonterminals on the RHS.
arnsholt
2009-03-09 01:02:42
I stand corrected. I read the following "Every grammar in Chomsky normal form is context-free, and conversely, every context-free grammar can be efficiently transformed into an equivalent one which is in Chomsky normal form." and came to the wrong conclusion.
Bill the Lizard
2009-03-09 01:14:40
+2
A:
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.
arnsholt
2009-03-09 00:58:53
I think from your amendment (edit) plus what I read at the Wikipedia links, that CNF is a restrictive case of BNF. All CNF grammars are in BNF; converting an arbitrary CFG in BNF to CNF is probably not entirely trivial (lots of introduced non-terminals), but seems to be doable.
Jonathan Leffler
2009-03-09 02:25:15
Sort of. CNF is a restriction on CFGs, while BNF is a way of encoding a CFG (remember, the N is Naur, not Normal). But there are other ways of encoding CFGs, for example the arrow notation in the Wikipedia articles. BNF (and its descendants) are just the most common way to do it in computing.
arnsholt
2009-03-09 02:39:44
+1
A:
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.
Jason M
2009-10-12 20:31:33
The last time I used JFLAP this was the case, its also handy to draw out DFS trees.
Woot4Moo
2010-10-07 15:48:52