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


1 Answer 1


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
    Commented Jul 3, 2018 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$ Commented Jul 3, 2018 at 23:00

Your Answer

By clicking β€œPost Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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