Non Context Free languages, what are they?

Question

I'm having alot of trouble understanding non context free languages. Simply put, are they recursively enumerable? As in, can a turing machine be used to represent a non context free language? Is it even recognizable or co - recognizable by a Turing machine?

Answer 1

Plenty of non-context-free languages are recursive. Consider (a^n)(b^n)(c^n); a simple Turing machine for this language can run back and forth over the tape, removing one of each symbol in a pass, until all symbols are removed or it runs out of one kind of symbol before another. Recursive languages are also recursively enumerable.

The Chomsky hierarchy goes regular, context-free, context-sensitive, recursive (roughly). There are levels beyond this and even levels in-between and spanning these canonical ones.