HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
linearwhycanacceptautomataemptyboundedstring

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#66229, answer score: 7

Revisions (0)

No revisions yet.