I've been reading the decidablity and undecidability chapters in Sipser's "Intro to Theory of Computation" however I could not find an explanation on the existence of a language that is both non-context free and decidable.
The only reference to this was a simple language hierarchy diagram showing where the decidable/recognisable bounds were in relation to language types.
I'm unsure as to how I should approach this but I've thought about proving this by diagonlisation:
- Let $M$ be the set of all decideable Turing Machines, and $L$ the set of all languages that are context-free. (Assume finite alphabet)
- By drawing up and filling the table where each language corresponds to a Turing Machine, I was hoping that I could find a contradiction in some $m \in M$ where there is no corresponding language $l \in L$.
I know that this will not work as both $M$ and $L$ are countable.
Any ideas on how I should approach this?