# How can I show that this language is context sensitive?

I have this language $$L=\{a^nb^nc^n,n\geq0\}$$, I know this language is not context free, but I don't know how to show that it is context sensitive, do I have to use a PDA?

• A language is context-sensitive iff it is accepted by some nondeterministic Turing machine using linear space. It is straightforward to come up with such a machine. – Yuval Filmus Nov 9 '20 at 19:04

In the same way that DFAs are the counterparts for regular expressions and PDAs are the counterparts for context free languages , the counterpart for context sensitive languages are LBAs (linear bounded Automaton)

That is to say that a language is context sensitive iff some LBA recognises it

But what are LBAs ?

Hopefully you have an idea about what Turing Machines are , an LBA is basically a Turing machine with limited memory , unlike Turing Machines which can access the entire infinite tape , the LBAs computation is restricted to the part of the tape which contains the input , thus the head can only operate in the part of the tape containing the input (hence bounded) , an Alternative less stricter definition is that only a finite contiguous portion of the tape, whose length is a linear function of the length of the initial input, can be accessed by the read/write head (hence linear) , in this way you can imagine the LBA as having a tape of length kn , where n is size of input and k is a constant associated with the machine

Now can we use an LBA to recognise L ?

Let M be an LBA : M on input w :

1. Read the first symbol make sure it is an a , else reject ( since n≥1 we can't accept the empty string)

2. Read the entire string and make sure it follows the right order as , then bs then cs then ds else reject

3. move the head to the left end of the tape then start crossing an a then a b then a c then a d

4. Repeat 3 till all as are crossed , when crossing symbols if M finds that w fell short of some symbol (ex: all bs are crossed but we need to cross a b) reject

5. after all as are crossed read the entire input if there remain any uncrossed symbols reject

6. else Accept

Clearly M is an LBA that recognises L , thus L is a context sensitive language

Notice how M uses only finite memory , in this example using only the portion of the tape where the input is written is enough to recognise L