Is the decidablity of the following question known?
Given a CFG G, is L(G) regular?
I've seen a bunch of decidability results in the world of CFLs, but I don't think I've ever seen this one, and can't find anything about it.
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.Sign up to join this community