*linear-bounded automaton (lba)*is a Turing machine whose tape is only kn squares long, where n is the length of the input (initial) string and k is a constant associated with the particular linear-bounded automaton.

Some textbooks define an lba to use only the portion of the tape that is occupied by the input; that is, k=1 in all cases. The definitions lead to equivalent classes of machines, because we can compensate for the shorter tape by having a larger tape alphabet.

**Theorem.**For every context-sensitive language L there exists an lba M such that L=L(M), that is, M accepts exactly the strings of L.

**Theorem.**For every language L accepted by an lba there exists a context-sensitive grammar that produces exactly L (or L - {}, depending on your definition of context-sensitive grammar).

We will not prove these theorems.

## No comments:

## Post a Comment