0
$\begingroup$

I know that if a language is regular or context free, the language is decidable. However, if a language is decidable does that imply that it is also regular or context free?

$\endgroup$
  • $\begingroup$ Your question title doesn't make much sense. You already know that every regular language is decidable; surely you can come up with some examples of those? $\endgroup$ – David Richerby Dec 18 '18 at 1:16
3
$\begingroup$

No.

As an example of a language that is decidable but does not have a context-free grammar is the language over the decimal digits that only contains the prime numbers.

$\endgroup$
1
$\begingroup$

$\{a^nb^nc^n \ |\ n\geq 0\}$ is one of the most famous non context-free languages. Consequently, it is also non regular. It is clearly decidable.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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