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$ 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.