I am having trouble understanding and pointing out when two different context-free grammars are structurally equivalent (at a very basic level). What are some clues/hints I should look for when determining if two CFG's are equivalent or not? Any help would be much appreciated.
1
votes
2 Answers
1
votes
Determining whether two CFGs are equivalent is an undecidable problem, so in general there is no good way to assert the equality of two CFGs.
1
votes
You don't say exactly what you mean by equivalence "structurally (at a very basic level)".
The well-known undecidability result concerns what is also called weak equivalence: Two grammars are equivalent if and only if they generate the same language (= set of words).
Undecidability means that there exists no general algorithm that solves every instance of this problem. Individual instances may still be easy to solve (and you can probably think of examples).
In fact, there is a large subclass of the context-free languages for which weak equivalence is decidable: the deterministic context-free languages. Unfortunately, existance of an algorithm in this case does not mean that the algorithm is efficient.
However, if by structural equivalence you mean something like "only renaming nonterminals" or "generating parse trees of the same shape", this may be a simpler problem.
