CODEWITHSUNDEEP
context-free-grammarturing-machines
Meraj Patel
Meraj Patel

Reputation: 129

Non Context Free languages, what are they?

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?

Upvotes: 1

Views: 1444

Answers (1)

Patrick87
Patrick87

Reputation: 28332

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.

Upvotes: 1

Related Questions