Context-Sensitive Grammars & Linear Bounded Automata

1. Context-Sensitive Grammars (Type-1)

While unrestricted grammars can model any computable process, they are often more powerful than needed. By introducing a single, critical constraint, we arrive at Context-Sensitive Grammars.

Let's begin with a video that formally defines this type of grammar and its production rules.

As the video explained, a grammar is Context-Sensitive (CSG) if its production rules are non-contracting (or length-increasing).

Formally, a grammar $G=(V,T,P,S)$ is a CSG if all its production rules in $P$ are of the form:
$\alpha \to \beta$
where $\alpha \in (V\cup T{)}^{\ast }V(V\cup T{)}^{\ast }$ and $\beta \in (V\cup T{)}^{+}$, with the crucial constraint that:
$|\alpha |\le |\beta |$

Let's break this down:

1. The left-hand side $\alpha$ must contain at least one non-terminal, just like in an unrestricted grammar.
2. The right-hand side $\beta$ must not be empty (it must contain at least one symbol).
3. The length of the left-hand side cannot be greater than the length of the right-hand side. This means that during a derivation, the sentential form can never get shorter.

(Note: There is a special exception for the empty string, $ϵ$. If the language includes $ϵ$, the rule $S\to ϵ$ is allowed, but only if the start symbol $S$ does not appear on the right-hand side of any other production.)

An Alternative (and the Original) Definition

The name "context-sensitive" comes from an equivalent, more restrictive definition where rules must be of the form:
$\alpha A\beta \to \alpha \gamma \beta$
Here, A is a single non-terminal, $\alpha$ and $\beta$ form the "context", and $\gamma$ is a non-empty string. This rule states that A can be replaced by $\gamma$ only when it appears in the specific context of being preceded by $\alpha$ and followed by $\beta$.

While the non-contracting definition ($|\alpha |\le |\beta |$) is more common today, it's useful to know that it is equivalent in generative power to the original context-based definition. For the rest of our course, we will primarily use the non-contracting definition.

Example: The aⁿbⁿcⁿ Language

We know the language $L=\{a^n{b}^n{c}^n\mid n\ge 1\}$ is not context-free. Let's see how a non-contracting grammar can generate it. Consider the following CSG:

• $S\to aSBC\mid aBC$
• $CB\to BC$
• $aB\to ab$
• $bB\to bb$
• $bC\to bc$
• $cC\to cc$

Notice the rule $CB\to BC$. Its LHS and RHS have the same length (2), so it's a valid non-contracting rule. However, its LHS is not a single non-terminal, so it's not a context-free rule. This "swapping" rule is what gives the grammar its power. It allows us to sort the generated Bs and Cs.

Let's derive aabbcc:

1. S $\Rightarrow$ aSBC (generates the outer a and c, and recursively calls S)
2. $\Rightarrow$ a(aBC)BC (replaces inner S with the base case aBC)
3. $\Rightarrow$ aaB(CB)C (grouping to show the target for the swap rule)
4. $\Rightarrow$ aaBBC C (applying CB -> BC)
5. $\Rightarrow$ a(aB)BCC (applying aB -> ab)
6. $\Rightarrow$ aabBCC
7. $\Rightarrow$ aa(bB)CC (applying bB -> bb)
8. $\Rightarrow$ aabbCC
9. $\Rightarrow$ aab(bC)C (applying bC -> bc)
10. $\Rightarrow$ aabbcC
11. $\Rightarrow$ aabb(cC) (applying cC -> cc)
12. $\Rightarrow$ aabbcc

The derivation only produces strings that are growing in length or staying the same length, never shrinking.

2. Linear Bounded Automata (LBAs)

Just as Finite Automata recognize regular languages and Pushdown Automata recognize context-free languages, there is a machine model for context-sensitive languages: the Linear Bounded Automaton (LBA).

An LBA can be thought of as a non-deterministic Turing Machine with a finite tape. However, the tape isn't of a fixed size. Instead, its size is determined by the input string itself.

Let's watch a video that describes the LBA model and its formal components.

As the video and diagram illustrate, the key features of an LBA are:

• It is a non-deterministic Turing Machine. Nondeterminism is essential to its power.
• Before computation begins, the input string w is placed on the tape, and it is enclosed by two special end markers, often denoted ⊢ (left marker) and ⊣ (right marker).
• The read/write head can move left and right and modify the tape content between the markers, but it is forbidden from moving past them.
• This means the amount of memory (tape space) available for computation is directly proportional to—or linearly bounded by—the length of the input string. This links directly to the concept of linear space complexity, O(n).

Formal Definition of an LBA

A Linear Bounded Automaton is a non-deterministic Turing Machine, which can be defined as a 7-tuple $M=(Q,\Sigma ,\Gamma ,\delta ,q_0,F,B)$, but with two additional constraints on its transition function $\delta$:

1. The left end marker ⊢ cannot be overwritten, and the head must move right when it reads ⊢. A typical transition would be δ(q, ⊢) = (p, ⊢, R).
2. The right end marker ⊣ cannot be overwritten, and the head must move left when it reads ⊣. A typical transition would be δ(q, ⊣) = (p, ⊣, L).

These two rules effectively "fence off" the working area of the tape to be exactly the length of the original input.

The language accepted by an LBA M, denoted L(M), is the set of all strings w for which M enters an accepting state.

The fundamental theorem connecting our two new concepts is:

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

Conclusion

In this lesson, we have filled a crucial gap in the Chomsky Hierarchy. We moved down from the all-powerful unrestricted grammars to a more constrained, yet still very powerful, class of grammars and machines.

Key Takeaways:

• A Context-Sensitive Grammar (CSG) is a grammar whose production rules are non-contracting, meaning the length of the left-hand side is less than or equal to the length of the right-hand side ($|\alpha |\le |\beta |$).
• This non-contracting property means that sentential forms can never shrink during a derivation. This prevents the grammar from generating all recursively enumerable languages but makes it more powerful than a context-free grammar.
• A Linear Bounded Automaton (LBA) is a non-deterministic Turing Machine whose available tape is restricted to the cells containing the initial input. Its memory is therefore linearly proportional to the input size.
• CSGs are the grammatical counterpart to LBAs.

Preview of the Next Lesson:
We have defined CSGs and LBAs, and we've stated that they are equivalent. In our next lesson, we will briefly explore the logic behind this equivalence. Then, we will assemble all the pieces we've learned—Regular, Context-Free, Context-Sensitive, and Unrestricted grammars—to formally present the Chomsky Hierarchy and illustrate the precise relationships of containment between these language classes.