2. Key Characteristics of Context-Sensitive Grammars

• Context Dependence
  Replacement of a non-terminal depends on its surrounding context (α and β). The rule applies only if the non-terminal appears with the specified neighbors.
• Non-Shortening Rules
  Production rules do not reduce the length of the string:
  |α A β| ≤ |α γ β|
  Exception: Some definitions allow S → ε only if the empty string belongs to the language.
• Non-Terminal Replacement in Context
  The grammar allows replacing non-terminals only under specific surrounding conditions.

 

3. Examples of Context-Sensitive Grammars

Example 1: Grammar for aⁿ bⁿ cⁿ, where n ≥ 1

This language cannot be generated by any context-free grammar, but can be generated by a context-sensitive grammar:

G = ({S, B, C}, {a, b, c}, P, S)

Production Rules (P):

• S → a B C
• S → a S B C
• C B → B C
• a B → a b
• b B → b b
• b C → b c
• c C → c c

This grammar generates strings like:
aⁿ bⁿ cⁿ, for n ≥ 1

Example 2: Context Dependence Illustration

Productions:

• S → a A B C
• A B → B B

In this case, A is replaced by B only when it is directly followed by B, showing clear context dependence.

4. Key Concepts Related to CSGs

• Derivation
  Sequence of production rules applied to derive a string, considering the surrounding context.
• Parse Tree
  A graphical representation of the derivation. The structure is more complex than CFG parse trees due to context-sensitive rules.
• Linear Bounded Automata (LBA)
  CSGs are equivalent to LBAs, which are Turing machines with restricted memory (the tape is limited to the length of the input).

 

5. Relationship to Linear Bounded Automata

• Every Context-Sensitive Grammar corresponds to a Linear Bounded Automaton that accepts the same language.
• LBAs are restricted Turing machines with memory proportional to the input size.
• Context-sensitive languages lie between context-free and unrestricted languages in the Chomsky hierarchy.

6. Importance of Context-Sensitive Grammars

• CSGs are essential in formal language theory.
• Applications include:
• Natural language processing
• Compiler design
• Modeling complex language structures

CSGs offer a balance between expressiveness and computability, extending beyond the limitations of context-free grammars while maintaining practical constraints.

Identifying Context-Sensitive Grammars (CSGs)

Context-sensitive grammars (CSGs) are more complex to identify than context-free grammars. Follow these guidelines to identify a CSG:

1. Check the Form of Production Rules

• CSGs have rules of the form:
  α A β → α γ β

Where:

• A is a non-terminal
• α and β are strings of terminals and/or non-terminals (the context)
• γ is a non-empty string of terminals and/or non-terminals
• The key idea: The replacement of A depends on its surrounding context (α and β)
• Length condition:
  |α A β| ≤ |α γ β|
  Meaning, no production can shorten the string, except possibly the rule S → ε if the empty string belongs to the language

2. Look for Context Dependence

• Check if the replacement of a non-terminal depends on neighboring symbols
• If a production applies differently based on what symbols appear around a non-terminal, the grammar is likely context-sensitive

3. Check for Non-Shortening Rules

• Ensure no rule reduces the overall length of the string (except possibly S → ε)
• Most CSGs prevent shortening to maintain structure

4. Consider the Language Generated

• Some languages are known to be context-sensitive but not context-free
• Example: L = { aⁿ bⁿ cⁿ | n ≥ 1 } is a classic context-sensitive language

5. Examples

Example 1: Context-Sensitive Grammar
Production: a A b → a B b

• Here, A is replaced by B only when surrounded by a and b
• Context-dependent → This is context-sensitive

Example 2: Context-Sensitive Grammar for L = { aⁿ bⁿ cⁿ | n ≥ 1 }
Productions:

• S → a B C
• S → a S B C
• C B → B C
• a B → a b
• b B → b b
• b C → b c
• c C → c c

Explanation:

• The rule C B → B C applies only when C is followed by B, showing context sensitivity

Example 3: Not Context-Sensitive (Context-Free)
Productions:

• A → a A
• A → b

Explanation:

• A is replaced independently of surrounding symbols → This is context-free

Example 4: Not Context-Sensitive (Unrestricted Grammar)
Production:

• A B → ε

Explanation:

• This rule shortens the string, which is not allowed in CSGs (except for S → ε)
• This may belong to a Type-0 (unrestricted) grammar

 

6. Use the Pumping Lemma

• If you suspect a language is context-sensitive:
• Apply the Pumping Lemma for context-free languages
• If the language fails the pumping lemma for CFGs, it might be context-sensitive (but not guaranteed)

7. Consider the Recognizing Automaton

• Context-sensitive languages are recognized by Linear Bounded Automata (LBA)
• If an LBA can be constructed for the language, it indicates context sensitivity

8. Challenges in Identifying CSGs

• Context dependencies can be subtle and hard to detect
• Unlike CFGs, no universal parsing algorithm exists for CSGs

9. Summary of Context-Sensitive Grammars

• CSG Requirement: Replacement depends on the surrounding context
• Production Form:
  α A β → α γ β
• A is replaced based on its neighbors α and β
• Non-Shortening Condition: Length does not decrease (except S → ε)
• Not a CSG if:
• Rules apply independently of context
• Rules shorten the string improperly