Some of the things I've learned every day since Oct 10, 2016
27: 2 Undecideable Problems in Context-Free Grammars
November 6, 2016Posted by on
A couple undecideable problems regarding context-free grammars:
- Equality: Given 2 distinct CFGs, do they produce/describe the same language?
- Disjointness: Again given 2 distinct CFGs, is there any string which can be produced by both?