CSGs and LBAs: Understanding the Connection

The Equivalence of CSGs and LBAs

The core relationship is stated by a theorem, sometimes known as the Kuroda-Myhill theorem:

Theorem: A language is context-sensitive if and only if it is accepted by a Linear Bounded Automaton.

To understand this, we need to see how to get from a grammar to a machine, and from a machine back to a grammar.

1. If L is a CSL, then L is accepted by an LBA. (CSG $\Rightarrow$ LBA)
2. If L is accepted by an LBA, then L is a CSL. (LBA $\Rightarrow$ CSG)

Let's explore each direction.

Part 1: From Context-Sensitive Grammar to Linear Bounded Automaton (CSG $\Rightarrow$ LBA)

If we have a language $L$ generated by a CSG, how can we build an LBA that accepts exactly the strings in $L$?

The key idea is to have the LBA perform a reverse derivation. Given an input string $w$, the LBA will try to work backward through the grammar's production rules to see if it can reach the start symbol $S$. If it can, the string $w$ must be in the language.

Here's how the LBA operates:

1. The input string $w$ is placed on the LBA's tape.
2. The LBA non-deterministically chooses a production rule from the CSG, say $\alpha \to \beta$.
3. It non-deterministically finds a substring on its tape that matches $\beta$.
4. It replaces that occurrence of $\beta$ with $\alpha$.
5. The LBA repeats steps 2-4. If the tape ever contains only the start symbol $S$ (followed by blanks), the LBA halts and accepts.

Why does this work on an LBA?

The crucial property is that CSGs are non-contracting. Every rule $\alpha \to \beta$ satisfies $|\alpha |\le |\beta |$. When our LBA works in reverse, it replaces $\beta$ with $\alpha$. This means the string on the tape will either shrink or stay the same length. It will never grow larger than the original input string $w$.

Since the working tape space never needs to exceed the initial length of $w$, all computations can be contained within the linear bounds of the LBA's tape.

To see a more formal description of this process, please read the first part of the proof in the following resource.

Part 2: From Linear Bounded Automaton to Context-Sensitive Grammar (LBA $\Rightarrow$ CSG)

This direction is more intricate. Given an LBA, how do we construct a CSG that generates the exact same language the LBA accepts?

The strategy is to make the grammar simulate the LBA's computation. The non-terminal symbols of our grammar will be complex, encoding the entire state of the LBA's computation at any given step.

This is often conceptualized as a "two-track" system:

• Track 1 (Bottom): Stores the final terminal string that we want to generate.
• Track 2 (Top): Simulates the LBA's computation on that string, including the current state and head position.

A non-terminal in our grammar might look like [q, X, a], which could mean: "The LBA is in state q with its head over this cell, the cell currently contains symbol X, and the final terminal symbol for this cell is a."

The grammar's derivation will proceed in three main phases:

1. Initialization: A set of starting rules generates a string of these complex non-terminals, representing the initial configuration of the LBA on some input $w$. This string effectively sets up the two tracks.
2. Computation Simulation: The core of the grammar consists of production rules that mimic the LBA's transition function, $\delta$.
   • A right move δ(p, X) = (q, Y, R) would correspond to a grammar rule like [p,X][Z] → [Y][q,Z], which moves the state q to the next symbol.
   • A left move δ(p, X) = (q, Y, L) would correspond to a rule like [Z][p,X] → [q,Z][Y].
     These rules are carefully constructed to be non-contracting; they just shift the state information around within the sentential form.
3. Cleanup: If the simulated computation reaches an accepting state, a final set of rules cleans up the simulation track, leaving only the terminal symbols from the bottom track. For example, a rule like [q_accept, X, a] → a would convert the complex non-terminal into its final terminal symbol a.

The following resource provides a concise, rule-based summary of how this simulation works.

Given your experience with systems design, you can think of this construction as a form of transpilation: we are compiling the operational logic of one system (the LBA's transition function) into the declarative rules of another system (the CSG's productions). The complexity of the grammar's non-terminals is necessary to carry the state required to faithfully simulate the automaton.

Conclusion

Today we've confirmed the deep and precise relationship between Context-Sensitive Grammars and Linear Bounded Automata. They are two sides of the same coin, describing the same class of languages.

Key Takeaways:

• CSG to LBA: An LBA can recognize a context-sensitive language by running a grammar's derivation in reverse. The non-contracting nature of CSG rules ($|\alpha |\le |\beta |$) guarantees that the LBA's tape usage will never exceed the length of the original input, fitting within its linear bounds.
• LBA to CSG: A CSG can generate the language of an LBA by simulating its computation. The grammar uses complex non-terminals to encode the LBA's configuration (state, head position, tape content) and has production rules that mimic the LBA's transitions. This construction yields a non-contracting grammar.
• This equivalence firmly establishes the LBA as the machine counterpart to CSGs, just as finite automata are to regular grammars and pushdown automata are to context-free grammars.

Preview of the Next Lesson:
We have now defined and related all the major language classes and their corresponding machines. In the next lesson, we will put it all together to formally present the Chomsky Hierarchy. We will illustrate the strict, nested containment of these language families (Regular $\subset$ Context-Free $\subset$ Context-Sensitive $\subset$ Recursive $\subset$ Recursively Enumerable) and summarize their defining characteristics.