Examples
An example of a context-sensitive language that is not context-free is L = { ap : p is a prime number }. L can be shown to be a context-sensitive language by constructing a linear bounded automaton which accepts L. The language can easily be shown to be neither regular nor context free by applying the respective pumping lemmas for each of the language classes to L.
An example of recursive language that is not context-sensitive is any recursive language whose decision is an EXPSPACE-hard problem, say, the set of pairs of equivalent regular expressions with exponentiation.
Read more about this topic: Context-sensitive Language
Famous quotes containing the word examples:
“Histories are more full of examples of the fidelity of dogs than of friends.”
—Alexander Pope (1688–1744)
“No rules exist, and examples are simply life-savers answering the appeals of rules making vain attempts to exist.”
—André Breton (1896–1966)
“There are many examples of women that have excelled in learning, and even in war, but this is no reason we should bring ‘em all up to Latin and Greek or else military discipline, instead of needle-work and housewifry.”
—Bernard Mandeville (1670–1733)