For example: This looks like a context free grammar: 𝑆 → 𝑄𝑅𝑇 𝑄 → 𝑎𝑄 | 𝑎 𝑅 → 𝑏𝑅 | 𝑏 𝑇 → 𝑐𝑇 | c

but it can be reduced to this regular language: 𝑆 → 𝑎𝑆 | 𝑎𝑅 𝑅 → 𝑏𝑅 | 𝑏𝑇 𝑇 → 𝑐𝑇 | c

I want to know if it is possible or not and why


It is not possible: it is undecidable whether a context-free grammar describes a regular language. For a proof, see e.g. Undecidable Problems for Context-free Grammars by Hendrik-Jan Hoogeboom.

  • $\begingroup$ And for knowing what kind of grammar it is without reducing, is it possible to use a turing machine to find that out? $\endgroup$ – jvrhjvrh Jul 3 '18 at 22:24
  • $\begingroup$ Yes. You only need to verify some constraints on the shape of its rules. We can do that, and so can a Turing machine. $\endgroup$ – reinierpost Jul 3 '18 at 23:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.