2
$\begingroup$

I'm struggling to understand some concepts related to the relationship between language and computability theories.

Can we convert decision problems to the corresponding grammars describing the languages? Can every decidable decision problem be converted to a context-free or context-sensitive grammars?

If it does not make sense at all, what is the relationship between the decision problems and languages?

$\endgroup$
  • $\begingroup$ Are you aware that general/unrestricted grammars are equivalent in expressive power to Turing machines? So that connection should be immediate (and a construction in the proof you should find in any textbook on the matter). $\endgroup$ – Raphael Sep 1 '14 at 10:54
3
$\begingroup$

Yes, every decision problem can be converted into a grammar that generates exactly the "yes"-instances of the problem.

And no, even if the problem is decidable, there is not necessarily a context-sensitive (let alone a context-free) grammar. An example would be the equivalence problem for regular expressions with exponentiation. (reference)

$\endgroup$

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.