# Why can't linear bounded automata accept an empty string?

The linear bounded automata (LBA) is defined as follows:

A linear bounded automata is a nondeterministic Turing machine $M=(Q,\Sigma,\Gamma,\delta,q_0,\square,F)$ (as in the definition of TM) with the restriction that $\Sigma$ must contain two symbols $[$ and $]$, such that $\delta(q_i,[)$ can contain only elements of the form $(q_j,[,R)$ and $\delta(q_i,])$ can contain only elements of the form $(q_j,],L)$

Informally this can be interpreted as follows:

In linear bounded automata, we allow the Turing machine to use only that part of the tape occupied by the input. The input can be envisioned as bracketed by left end marker $[$ and right end marker $]$. The end markers cannot be rewritten, and RW head cannot move to the left of $[$ or to the right of $]$.

Now I read that context sensitive grammar imitates the function of LBA and is defined as follows:

A grammar is CSG if all productions in context sensitive grammar takes form $$x\rightarrow y,$$ where $x,y\in(V\cup T)^+$ and $|x|\leq|y|$

Now people say that CSG cannot contain lambda or empty production (which takes form: $x\rightarrow \lambda$) as it will make make it impossible to meet the requirement $|x|\leq|y|$ and this can be understood.

However, what I don't understand is how informal interpretation of the working of LBA given above explains why LBA cannot accept empty string (which is why CSG does not have lambda production). Can anyone explain?

• So CSG do not imitate exact behavior of LBAs (as LBAs can produce empty string). Also in the definition of Context Sensitive Languages, we allow $\lambda$ so that it becomes proper superset of Context Free Languages. When we allow $\lambda$ in both mechanical counterpart (LBAs) and language counterpart (CSLs), why do we have the concept of grammar (CSG) without $\lambda$ production at first place? In other words, why CSG is usually defined to not have $\lambda$ production at first place? Commented Nov 19, 2016 at 17:09
• also I am quite anxious if your statement "there is an equivalence between LBAs not accepting the empty string and CSGs." is correct. Peter Linz's book (4th edition) has theorem 11.9: "If language L is accepted by some LBA, then there exist a CSG that generates L". In the proof it says: "production $\square\rightarrow \lambda$ can be omitted as it is necessary only when the Turing machine moves outside the bounds of the original input, which is not the case here." Also it seems to somewhat explain my concern of why LBAs do not accept the empty string, but still those words sound fuzzy. Commented Nov 19, 2016 at 17:09