[Home]History of Context-sensitive language

HomePage | Recent Changes | Preferences

Revision 5 . . October 12, 2001 8:36 am by AxelBoldt [*Example]
Revision 4 . . (edit) August 26, 2001 11:41 pm by Jan Hidders
  

Difference (from prior major revision) (no other diffs)

Added: 6a7,14

Examples




Every context-free language is context-sensitive.

An example of a context-sensitive language that is not context-free is L = { an : n is a prime number }. The easiest way to show this is using a linear bounded Turing machine.




HomePage | Recent Changes | Preferences
Search: