Motivation
Context-free rules rewrite one variable regardless of its surroundings, which is why a stack suffices and why is out of reach. To generate such a language, a grammar must be able to move symbols around and compare counts of three blocks at once. The grammars studied here allow rules whose left side is a longer string, with one restriction that keeps derivations under control: a rule may never shorten the sentential form. That single restriction has two large consequences. It bounds the length of every intermediate form in a derivation of a fixed terminal word, and it shows that the generated languages can be recognized by a machine that never leaves the portion of the tape that holds its input.
We prove a complete example, the length lemma, the decidability of acceptance on a bounded tape, and the direction from grammars to bounded-tape machines. The converse direction, from bounded-tape machines to grammars, is deferred: it is not proved here, and no statement below relies on it. We also make no claim about whether deterministic and nondeterministic bounded-tape machines accept the same languages.
Definitions
Definition 4.1.1
(Noncontracting grammar)
A noncontracting grammar is where every rule has the form with , contains at least one variable and . One exception is allowed: the rule may be present, provided occurs on no right-hand side. Derivations , and are defined as for context-free grammars, with a step replacing an occurrence of by .
We call a language context-sensitive if it is generated by a noncontracting grammar. There is also a stricter rule shape with that gives the same class of languages; that equivalence is a standard theorem which is not proved here, so every statement below concerns noncontracting grammars only.
Definition 4.1.2
(Linear bounded automaton)
A linear bounded automaton (LBA) is a nondeterministic Turing machine with tape alphabet containing two endmarkers . On input the tape holds , and the head starts on . A transition reading must write and move right; one reading must write and move left; no other transition may write an endmarker. Hence the machine uses exactly the cells holding the input, plus the two endmarkers. It accepts if some computation reaches .
A configuration on an input of length is a triple (state, contents of the interior cells, head position among the cells). The endmarker cells never change, so they need not be recorded.
Definition 4.1.3
(Length-nondecreasing derivations)
For a noncontracting grammar, a derivation is called monotone if .
Theorems
Theorem 4.1.4
(Length lemma and decidable membership)
Let be noncontracting and with . If , then the derivation never uses , is monotone, and every sentential form in it has length at most . Consequently membership of in is decidable by exploring the finitely many strings over of length at most .
Theorem 4.1.5
(A grammar for )
The grammar with start variable and rules , , , , , is noncontracting and generates exactly .
Theorem 4.1.6
(Acceptance by a bounded-tape machine is decidable)
Let be an LBA and an input of length . The number of configurations is at most , and accepts if and only if it has an accepting computation of fewer than steps. Hence there is an algorithm, for LBAs given as data, that decides whether accepts .
Theorem 4.1.7
(From a noncontracting grammar to an LBA)
For every noncontracting grammar there is an LBA with .
Theorem 4.1.8
(A deterministic marking algorithm)
There is a deterministic LBA, using only cell contents from and the endmarkers, that accepts exactly the words with , in steps.
Proof sketch or proof idea
Proof
(Length lemma and decidable membership)
Length lemma. A rule applied in a derivation replaces by with , with the single exception . That exception requires an occurrence of to rewrite, and because never occurs on a right-hand side, occurs only in the initial form , so the exception can only be the first step and it produces . For the exception is never used, so every step is non-shrinking, the derivation is monotone, and the last form is the longest. For decidability, the set of strings over of length at most is finite. Compute the set of strings in reachable from by applying rules whose results stay in , iterating until nothing new is added; then iff is in the set, by the first part.
Proof
(Soundness and completeness of the three-block grammar)
The grammar for . Every rule has and each left side has a variable, so is noncontracting, and occurs on a right-hand side but there is no rule . For with : apply exactly times and then , obtaining . Use repeatedly, moving each left past all 's, to reach . Then turns the first into , each turns the next, and similarly followed by converts the 's from left to right.
For the converse we prove an invariant. Define two families of strings. Family one: with containing copies of and copies of . Family two: with , , and . We claim every sentential form reachable from is in one of the two families. The start form belongs to family one with . Applying to gives , which is in family one with ; applying gives , in family two with , . Now consider each rule applied to a family-two form . The rule needs an adjacent pair of uppercase letters; uppercase letters occur only in , so it acts inside and preserves the counts. The rule needs a lowercase directly followed by . The 's are the leading block and the symbol after them is the first symbol of if and the first symbol of if . So this rule applies only when and begins with , producing with , which is in family two with . The rule needs directly before : this happens only when , , and begins with , giving . The rule similarly needs , and beginning with , giving . The rule needs and beginning with , giving . In every case the conditions on counts are preserved because one uppercase letter becomes the corresponding lowercase letter. Rules acting on a family-one form are only the two -rules and inside ; the rules with or cannot apply because separates the 's from . So the claim holds. A terminal word contains no , or , so it lies in family two with , hence and the word is with .
Proof X-ray
What the invariant for the $a^n b^n c^n$ grammar is doing
Two facts are carried together: a counting fact (the number of 's, of -or-'s and of -or-'s are equal) and an ordering fact (all 's precede the 's, which precede the 's, with unresolved uppercase letters trailing). Counting is preserved because each rule either adds one of each letter type or relabels a letter. Ordering is the delicate part: a lowercase letter can only be created immediately after an existing lowercase letter ( after an or a , after a or a ), so the lowercase letters grow from left to right. The invariant also explains the dead ends in which a is stranded behind a lowercase : such forms satisfy the counting fact but can never become terminal.
Proof
(Acceptance on a bounded tape by shortest paths)
Acceptance on a bounded tape. A configuration is determined by the state ( choices), the interior cells ( choices) and the head position ( choices), which gives the bound . Think of configurations as vertices of a finite directed graph with an edge for each possible step. Acceptance means that some vertex with state is reachable from the initial vertex. A shortest path visits distinct vertices, so it has fewer than edges. A deterministic algorithm explores the graph, for instance breadth first, until no new vertex appears, and answers yes if a vertex in the accepting state was reached. A segment between repeated configurations is a cycle that can be deleted from an accepting path. In a nondeterministic machine, repetition need not force all future choices to loop; the shortest-path argument is what justifies removing it.
Proof
(Reverse derivations on a padded tape)
Grammar to LBA. Fix and an input with . If , accept exactly when is a rule. Let , and exclude the exceptional rule from every reverse-rule choice below; it cannot occur in a derivation of a nonempty word. Use an extra tape symbol , a padding symbol not in . The invariant is that the interior of the tape always has the form for a sentential form with . Initially . The machine repeats the following. First it checks whether the tape is ; if so it accepts. Otherwise it guesses a rule of and a position, and verifies by scanning that the cells there contain (the length of is bounded by a constant of , so this check uses finite memory). It replaces by , shifts the rest of the tape left by cells one symbol at a time, and writes symbols at the right end. The new tape is where is the reverse of the chosen step. All operations stay in the interior cells.
Correctness: if the machine accepts, the sequence of tape contents between rounds gives forms with , so . Conversely, if and , the length lemma provides a derivation whose forms all have length at most , so the machine can follow it backwards, choosing the appropriate rule and position at each round and finally accepting at . The machine is nondeterministic; this proof does not produce a deterministic machine.
Proof
(The marking rounds: correctness and cost)
Marking algorithm. Phase zero scans the input once with a fixed finite set of control states and rejects unless it is in ; let the counts be . A round begins at . It skips symbols , and if the next symbol is it replaces it by ; then it moves right across 's and 's to the first , which it replaces by ; then across 's and 's to the first , which it replaces by ; then it returns to . If an expected symbol is not found (the scan meets , or while looking for , or while looking for ) it rejects. If instead the first non- symbol is , no unmarked remains: it scans right and accepts exactly when only and appear before . After successful rounds the unmarked counts are , , . If or the round fails to find its symbol and rejects. If rounds succeed, no remains and the machine accepts iff no and no remain, that is iff . Each round costs steps and there are at most rounds.
Counterexample mode
The $\varepsilon$-exception cannot be dropped carelessly
Claim (false): the grammar is noncontracting, so the length lemma bounds its derivations by the length of the word. In fact is not permitted because occurs on a right-hand side. The derivation has lengths and shrinks at its last step, so the length lemma fails for it; deciding membership by examining forms of length at most would miss the intermediate form of length for . Repair: introduce a new start with rules and use . Now occurs on no right-hand side, every rule is noncontracting, and the language is unchanged.
Concept lensAlgorithmic
Reverse derivation as search on a bounded space
The simulation does not generate words; it starts from the input and searches backwards for a derivation. Each tape content is a node of a finite graph (strings of length over a finite alphabet), and each reverse rule application is an edge. The length lemma is what keeps the graph finite and the padding trick makes every node fit in cells. Acceptance is reachability of the single node from the node .
Worked examples
Worked example 4.1.9
(Deriving aabbcc)
With : . The steps use, in order, , , on the middle pair, , , and . The lengths are , nondecreasing as the lemma requires. The final form has two of each letter, matching the counting invariant.
Worked example 4.1.10
(A derivation that cannot finish)
Start as before: . Apply at the second to get , and then to get . The is now preceded by the lowercase . No rule has a left side ending in , and needs an uppercase to its left, so no rule applies to this . The form satisfies the counting invariant but has the uppercase letters after a lowercase ; it can never become terminal, which is consistent with the second family in the proof requiring that lowercase letters be created from left to right.
Worked example 4.1.11
(Reverse derivation of aabbcc on a tape of six cells)
Write the tape with padding symbol . Start: . Reverse : . Reverse : . Reverse : . Reverse : . Reverse at the middle pair: . Reverse on the block starting at position two: the block is replaced by and the remainder shifts left by two cells: . Reverse : the four cells become and the tape is . This is the accepting tape content for , so the machine accepts. All forms have length at most , as the length lemma guarantees.
Worked example 4.1.12
(The marking algorithm on aabbcc)
After phase zero confirms the shape , round one marks the first , the first and the first : . Round two marks the remaining ones: . At the start of round three, after skipping 's the head meets , so no remains; scanning right finds only and until , and the machine accepts. For , round one gives and round two marks and giving but then finds no unmarked and rejects.
Common mistakes
Common mistake
(The empty word enters only through the protected start rule)
A common error is to say that noncontracting rules forbid in the language. The exception for with absent from right-hand sides is exactly what allows the empty word.
Common mistake
(CB to BC is not a harmless reordering)
The rule is the only rule that moves uppercase letters, and it makes the counting comparison possible. It must bring every in front of every before the 's are converted; otherwise a can be stranded behind a lowercase , as in the second worked example.
Common mistake
(Do not read more into the LBA results than was proved)
It is a mistake to say that an LBA can use "as much tape as it likes". As defined here it uses exactly the input cells and the two endmarkers, and no other space bound is part of the definition. Finally, do not infer from the grammar-to-LBA theorem that every LBA language has a grammar, or that deterministic and nondeterministic machines have been compared. Those statements are outside what was proved.
Summary
Noncontracting grammars cannot shrink sentential forms, which bounds every derivation of a nonempty word by the length of the word and makes membership decidable. The grammar for is verified by an explicit invariant. A bounded-tape machine has finitely many configurations, so its acceptance is decidable. Every noncontracting grammar is simulated by an LBA that runs derivations backwards in a padded tape. The converse is deferred, and no claim about determinism is made.
Exercises
Quick check
(Derive in the grammar of the second theorem and count the steps.)
Solution · Answer
(three steps). Three swaps give (for example ). Then , , give (three steps), and , , give (three steps). Total: steps.
Quick check
(Trace the marking algorithm on and explain why it rejects.)
Solution · Answer
Phase zero accepts the shape . Round one produces . Round two marks the remaining and , giving , and then looks for an unmarked : it skips and reaches , so it rejects. The counts are unequal.
Quick check
(An LBA has states and tape alphabet of size . On input of length , bound the number of configurations by the formula in the third theorem.)
Solution · Answer
The bound is . Any accepting computation can be taken to have fewer than steps.
Quick check
(Let be noncontracting grammars with disjoint variable sets and no rules . Construct a noncontracting grammar for and prove correctness.)
Solution · Answer
Take the rules of both grammars together with a fresh start and the rules . These two new rules are noncontracting (lengths equal, left side a variable), and occurs on no right-hand side. A form derived from is or a form derived from one . A form derived from contains only variables of and terminals, and each rule of () has a left side with a variable of , so it cannot apply. Hence derivations from are exactly the derivations of or preceded by one step, and the language is the union.