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?

Improve this question
$\endgroup$
1
  • $\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, 2014 at 10:54

1 Answer 1

Reset to default
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)

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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