# Context Sensitive Languages

Context sensitive languages are those languages whose strings can be generated by a context sensitive grammar. This type of grammar is similar in form to a context free grammar (see Context Free Languages), but instead of rules of the form A -> X, where A is a non-terminal symbol and X is a string of terminals and non-terminals, a context sensitive grammar contains rules of the form X -> Y, where X and Y are strings of terminals and non-terminals, with the constraint that Y be at least as long as X. There is an exception to this rule, that if S is the starting symbol, and S never appears on the right side of a transition, then the transition S -> ε is allowed. This makes it possible for a grammar to generate the empty string.
An example of such a grammar is:
* S -> ε|aAbc|abc
* A -> aAbC|abC
* Cb -> bC
* Cc -> cc
This grammar generates the language $\{a^{n}b^{n}c^{n}|n\geq 0\}$, a language which is not context free.
An alternative definition for a context sensitive grammar is a grammar where each of transitions has the form YAZ -> YXZ, where A is a non-terminal, and X, Y and Z are all strings of terminals and non-terminals (Y and Z may empty). Because Y and Z remain unchanged, this fills the same function as a transition A -> X, but can use the context of A as a requirement for the transition. In 1, Noam Chomsky shows that these two definitions are equivalent, and produce the same languages.
Any context free grammar is also a context sensitive grammar under the second definition which only uses empty contexts, so the set of context free languages is a subset of the set of context sensitive languages. Since, in the example above, a context sensitive grammar can produce the language $\{a^{n}b^{n}c^{n}|n\geq 0\}$ while a PDA cannot, the context free languages must be a proper subset of the context sensitive languages.

## Linear Bounded Automata

The class of context sensitive languages is equivalent to the class of languages that can be recognized by linear bounded automata. A linear bounded automaton (LBA) is a deterministic machine based on a state, a "tape" that contains the input string, and a read/write head that moves left and right along the tape. The machine compares its current state and the symbol on the tape at the head's position with a finite number of rules to determine its next state, what symbol to write on the tape, and which direction (left/right) to move the tape head in. Similarly to both finite automata and pushdown automata, linear bounded automata accept or reject an input based on whether they halt in an accept state or not. An LBA halts when there are no rules for its current combination of state and character being read.
The only other restriction on an LBA is that the tape must be finite, with a size linearly derived from the size of the input string. For example, if a particular machine uses tapes 2*s+5 long, where s is the size of the input, then when processing a string of size 10, it would have a tape of length 25.

### Abilities

This design gives the LBA a great deal of computational freedom, and so it can recognize any languages whose space requirements for string recognition grow linearly. One example is the language $\{a^{n}b^{n}c^{n}d^{n}|n\geq 0\}$. This language can be recognized in space s+1, meaning that it only requires the section of the tape it was written on, plus a single blank character at the end. This is because unlike a PDA or DFA, an LBA need not deal with the input in sequence - it can (and does in the sample machine available below) mark off the characters in sets, first an 'a', then a 'b', then a 'c', then a 'd', and repeat. It will not accept if it does not exhaust all character types on the same run.
This language cannot be recognized by DFAs and PDAs, because they would have to count and store the number of 'a's as they went by. A DFA could only remember a number of 'a's equal to or fewer than its number of states, and so could not check the number of 'b's in an arbitrarily long string. A PDA could store the number of 'a's on the stack, but would necessarily destroy that information when comparing them to the 'b's, and thus could not compare it to the number of 'c's.

### Looping

Note that while it is possible for an LBA to enter an infinite loop, since there is only a finite tape, a finite number of symbols to put on it, and a finite number of states it can be in, the total number of conditions for a given machine and input is finite. That means that any infinite loop must, within a finite number of steps, return to a set of conditions it has already encountered. Also, since LBAs are deterministic, a machine that repeats its set of conditions will continue to repeat the loop it has just traversed indefinitely. These two statements show that an LBA is caught in an infinite loop (and thus will never accept or reject) if and only if it repeats its total conditions (including state, head position, and tape contents). Since $S\cdot T\cdot A^{T}$ is the total number of possible conditions, where S is the number of states, T is the size of the tape, and A is the size of the alphabet, any machine that runs through more than S*T*A^T steps must repeat a set of conditions, and thus be in an infinite loop. While this number may be quite large, it provides a definite, finite-time method of determining whether a given LBA will loop on a given input. The similar but more advanced Turing Machine (see Unrestricted Languages) will have no such method.

## Examples

The code below is a sample LBA emulator in Perl. Given the description of a machine and an input string, it simulates the machine processing the input string, and shows whether the machine accepts or not.
The syntax is: progname.pl LBAFile inputFile, where LBAFile is a text file containing the LBA instructions, and inputFile is a text file containing the input string. Some sample inputs, including a set of LBA instructions for a machine to recognize $\{a^{n}b^{n}c^{n}d^{n}|n\geq 0\}$, can be found under sample LBA inputs
Previous | Next