2
$\begingroup$

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?

Improve this question
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Nov 9 '20 at 19:04
3
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.