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?
$\begingroup$
$\endgroup$
1
-
$\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
Add a comment
|
$\begingroup$
$\endgroup$
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 :
Read the first symbol make sure it is an a , else reject ( since n≥1 we can't accept the empty string)
Read the entire string and make sure it follows the right order as , then bs then cs then ds else reject
move the head to the left end of the tape then start crossing an a then a b then a c then a d
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
after all as are crossed read the entire input if there remain any uncrossed symbols reject
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
