As I said in this post I am going to continue context sensitive languages and grammars.
Computationally the context-sensitive languages are equivalent with linear bounded non-deterministic Turing machine. That is a non-deterministic Turing machine with a tape of only kn cells, where n is the size of the input and k is a constant associated with the machine.
This means that every formal language that can be decided by such a machine is a context-sensitive language, and every context-sensitive language can be decided by such a machine.
This set of languages is also known as NLIN-SPACE, because they can be accepted using linear space on a non-deterministic Turing machine.
The class LIN-SPACE is defined the same, except using a deterministic Turing machine. Clearly LIN-SPACE is a subset of NLIN-SPACE, but it is not known whether LIN-SPACE=NLIN-SPACE. It is widely suspected they are not equal.
Showing posts with label context sensitive languages. Show all posts
Showing posts with label context sensitive languages. Show all posts
Thursday, May 10, 2007
Subscribe to:
Posts (Atom)