4
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

Linear-bounded automata are able to accept the empty string. The equivalence between linear-bounded automata and context-sensitive grammars needs to be cognizant of this discrepancy between the two models. Usually a context-sensitive grammar is allowed one extra product to optionally produce the empty string. Alternatively, there is an equivalence between LBAs not accepting the empty string and CSGs.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – anir123 Nov 19 '16 at 17:09
  • $\begingroup$ 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. $\endgroup$ – anir123 Nov 19 '16 at 17:09
  • $\begingroup$ From above excerpt does author indeed mean to imply that LBAs does not accept empty string? $\endgroup$ – anir123 Nov 19 '16 at 17:10
  • 2
    $\begingroup$ Some natural definitions of context-sensitive grammars have the unfortunate consequence that the grammar cannot generate the empty string, and this shortcoming has to be "patched". There is no such problem in LBAs – they most definitely can accept the empty string. The author wasn't implying anything – you are putting words into her mouth. $\endgroup$ – Yuval Filmus Nov 19 '16 at 20:26

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.