🧠 Introduction

🎯 Context-Sensitive Languages & LBAs

Context-sensitive languages (CSLs) are Type 1 in the Chomsky hierarchy. They're generated by context-sensitive grammars (CSGs) and recognized by linear bounded automata (LBAs). CSLs are more powerful than context-free languages but less powerful than recursively enumerable languages.

Key insight: The key restriction is that grammar rules are length non-decreasing — the string never shrinks. This corresponds to a Turing machine whose tape is bounded by the input length.

Why CSLs & LBAs Matter

Between CFL and TM: More power than CFG, less than TM. Context matters: Rules depend on context. Linear memory: Tape bounded by input. Decidable membership: PSPACE. Natural language: Some phenomena are context-sensitive. Theory: Completes the hierarchy.

📘 Type 1📏 Linear tape🔄 Context matters✅ Membership decidable

# Context-Sensitive Languages & LBAs — the big picture
print("""
=== The Position in the Hierarchy ===

  Regular ⊊ Context-Free ⊊ Context-Sensitive ⊊ R.E.
  (Type 3)   (Type 2)        (Type 1)          (Type 0)

Context-Sensitive Languages (CSLs):
  - Between CFL and R.E.
  - Generated by context-sensitive grammars
  - Recognized by linear bounded automata
  - More powerful than CFL
  - Less powerful than TM

=== Why "Context-Sensitive"? ===

Compare:

CONTEXT-FREE:
  A → α
  Replace A regardless of context.

CONTEXT-SENSITIVE:
  αAβ → αγβ
  Replace A only in context α_β.

"Context-sensitive" means the replacement
depends on the surrounding symbols.

=== Why "Linear Bounded"? ===

The grammar rules are length non-decreasing:
  |αγβ| ≥ |αAβ|

So the string never shrinks.
This means a machine recognizing the language
never needs more than linear space.

Hence: Linear Bounded Automaton (LBA).

=== The Key Properties ===

1. MORE POWERFUL THAN CFL
   - Can count multiple things
   - Can handle a^n b^n c^n
   - Can handle ww

2. LESS POWERFUL THAN TM
   - Membership is decidable
   - Emptiness is undecidable
   - Most problems undecidable

3. MEMBERSHIP: PSPACE
   - Decidable
   - But can be expensive

4. CLOSURE
   - Closed under union, intersection, complement
   - More closed than CFL!

=== Real-World Analogy ===

Imagine a Turing machine with a SHORT TAPE:
  - Tape length = input length
  - Can't use more space
  - Can still do complex computation
  - But limited by input size

This is an LBA.
It's more powerful than a PDA,
but less powerful than a full TM.
""")

# ANALOGY
print("=== Analogy: Fitting into a Small Notebook ===")
print("""
Imagine solving a problem with:
  - A notebook with exactly N pages (N = input size)
  - You can write, erase, rewrite
  - But you can't add more pages
  - You can't use more than N pages

This is an LBA!
  - Tape = notebook
  - Input = N pages
  - Can't exceed N
  - But can compute complex things

Compare:
  DFA: No notebook (just memory)
  PDA: Notebook with a stack (LIFO)
  LBA: Notebook with N pages (random access)
  TM: Notebook with unlimited pages

Each more powerful than the last.

=== Another Analogy: Puzzles ===

CSLs are like puzzles that:
  - Can be solved with the given pieces
  - Can't introduce new pieces
  - But can rearrange existing ones

Examples:
  - Jigsaw puzzles (rearrange pieces)
  - Rubik's cube (manipulate existing state)
  - Sudoku (fill in given grid)

These are "context-sensitive":
  - The solution depends on the given context
  - Can't add new information
  - But can compute complex arrangements
""")

# THE BIG PICTURE
print("""
=== The Big Picture ===

Context-Sensitive Languages:

  ┌─────────────────────────────────────┐
  │ Type 0: Recursively Enumerable      │
  │  ┌───────────────────────────────┐  │
  │  │ Type 1: Context-Sensitive     │  │
  │  │  ┌─────────────────────────┐  │  │
  │  │  │ Type 2: Context-Free    │  │  │
  │  │  │  ┌───────────────────┐  │  │  │
  │  │  │  │ Type 3: Regular   │  │  │  │
  │  │  │  └───────────────────┘  │  │  │
  │  │  └─────────────────────────┘  │  │
  │  └───────────────────────────────┘  │
  └─────────────────────────────────────┘

Type 1 sits between Type 2 and Type 0.

=== Key Facts ===

Grammar: αAβ → αγβ
  - Context on both sides
  - Length non-decreasing
  - No ε-productions (except S → ε)

Machine: Linear Bounded Automaton
  - Turing machine with tape bounded by input
  - More powerful than PDA
  - Less powerful than TM

Language class: Context-Sensitive Languages
  - Strictly contains CFL
  - Strictly contained in R.E.
  - Membership decidable (PSPACE)

=== Why Study CSLs? ===

1. NATURAL LANGUAGE
   Some linguistic phenomena are context-sensitive.
   Cross-serial dependencies in Dutch.
   Agreement patterns.

2. COMPLETE THE HIERARCHY
   Understanding all four levels.

3. THEORETICAL IMPORTANCE
   Between CFL and TM.
   Interesting properties.

4. PRACTICAL APPLICATIONS
   Some protocols, type systems, bioinformatics.

5. DECIDABILITY
   Membership is decidable (unlike TM).
   Useful for verification.
""")

# CSL IN CODE
print("=== CSL in Code: A Simple Example ===")

class CSL:
    """A simple context-sensitive language recognizer."""
    def __init__(self, max_length=20):
        self.max_length = max_length
    
    def accepts_anbncn(self, w):
        """Recognize a^n b^n c^n."""
        # Use a bounded simulation (LBA-style)
        # This is a simple O(n²) algorithm
        n = len(w)
        if n == 0:
            return True
        
        # Count a's
        i = 0
        while i < n and w[i] == 'a':
            i += 1
        a_count = i
        
        # Count b's
        while i < n and w[i] == 'b':
            i += 1
        b_count = i - a_count
        
        # Count c's
        while i < n and w[i] == 'c':
            i += 1
        c_count = i - a_count - b_count
        
        # Check all consumed and equal
        return i == n and a_count == b_count == c_count
    
    def accepts_ww(self, w):
        """Recognize ww (w ∈ {a,b}*)."""
        n = len(w)
        if n % 2 != 0:
            return False
        half = n // 2
        return w[:half] == w[half:]
    
    def accepts_anbncndn(self, w):
        """Recognize a^n b^n c^n d^n."""
        n = len(w)
        if n == 0:
            return True
        
        # Parse blocks
        i = 0
        counts = []
        for symbol in ['a', 'b', 'c', 'd']:
            start = i
            while i < n and w[i] == symbol:
                i += 1
            counts.append(i - start)
        
        return i == n and len(set(counts)) == 1


csl = CSL()

print("Context-Sensitive Language Recognizers:")
print()

# a^n b^n c^n
print("L1 = { a^n b^n c^n | n ≥ 0 }:")
for w in ['', 'abc', 'aabbcc', 'aaabbbccc', 'ab', 'aabbc', 'aabbbcc']:
    result = "✓" if csl.accepts_anbncn(w) else "✗"
    print(f"  '{w}' → {result}")

# ww
print("\nL2 = { ww | w ∈ {a,b}* }:")
for w in ['', 'aa', 'abab', 'aabb', 'ab', 'aab', 'ababab']:
    result = "✓" if csl.accepts_ww(w) else "✗"
    print(f"  '{w}' → {result}")

# a^n b^n c^n d^n
print("\nL3 = { a^n b^n c^n d^n | n ≥ 0 }:")
for w in ['', 'abcd', 'aabbccdd', 'abc', 'aabbcc', 'aabbccd']:
    result = "✓" if csl.accepts_anbncndn(w) else "✗"
    print(f"  '{w}' → {result}")

print("""
=== Key Observations ===

1. CSLs can count MULTIPLE things:
   - a^n b^n c^n (three counts)
   - a^n b^n c^n d^n (four counts)
   
   CFGs can only count ONE thing.
   CSGs can count multiple.

2. CSLs can handle COPYING:
   - ww (copy)
   - Requires remembering entire first half
   
   CFGs can't do this.
   CSGs can.

3. CSLs use LINEAR SPACE:
   - Need to store the input
   - Can't use more than O(n) space
   - But can use the space in complex ways

4. MEMBERSHIP IS DECIDABLE:
   - Can simulate LBA
   - Uses O(n) space
   - May take exponential time
   - But always halts
""")

📝 Context-Sensitive Grammars

🎯 Formal Definition

A context-sensitive grammar (CSG) is a formal grammar where every production rule is of the form αAβ → αγβ, where A is a nonterminal, α and β are strings of symbols (possibly empty), and γ is a non-empty string. The key property is that rules are length non-decreasing.

CSG Components

Rule form: αAβ → αγβ. Context: α and β. Non-empty: γ ≠ ε. Length: |αγβ| ≥ |αAβ|. ε-rule: Only S → ε allowed. Equivalent: Non-contracting grammars.

📝 αAβ → αγβ🔄 Context📏 Non-decreasing🚫 No ε

# Context-Sensitive Grammars
print("=" * 60)
print("CONTEXT-SENSITIVE GRAMMARS")
print("=" * 60)

print("""
=== Formal Definition ===

A CONTEXT-SENSITIVE GRAMMAR (CSG) is a 4-tuple:
  G = (V, Σ, R, S)

where:
  V: finite set of nonterminals
  Σ: finite set of terminals (V ∩ Σ = ∅)
  R: finite set of rules of the form αAβ → αγβ
  S: start symbol (S ∈ V)

Rule restrictions:
  - A ∈ V (single nonterminal)
  - α, β ∈ (V ∪ Σ)* (context)
  - γ ∈ (V ∪ Σ)+ (non-empty)
  - |αγβ| ≥ |αAβ| (length non-decreasing)

Exception: S → ε is allowed if S doesn't appear on RHS.

=== Why "Context-Sensitive"? ===

The rule αAβ → αγβ says:
  "Replace A with γ ONLY when A appears
   in the context α_β"

Contrast with context-free:
  A → γ (always replace A with γ)

The context matters!

=== Length Non-Decreasing ===

For any rule αAβ → αγβ:
  |αγβ| = |α| + |γ| + |β|
         ≥ |α| + 1 + |β|    (since |γ| ≥ 1)
         = |α| + |A| + |β|
         = |αAβ|

So the string never shrinks.
This is the KEY property of CSGs.

=== Equivalent Formulations ===

CSGs are equivalent to:
  1. NON-CONTRACTING GRAMMARS
     Rules: α → β with |β| ≥ |α|
     
  2. MONOTONIC GRAMMARS
     Rules: α → β with |β| ≥ |α|
     (Same as non-contracting)
     
  3. TYPE 1 GRAMMARS
     Standard definition.

All generate the same class (CSLs).

=== Examples ===

1. L = a^n b^n c^n
   S → aSBC | aBC
   CB → BC
   aB → ab
   bB → bb
   bC → bc
   cC → cc

   How it works:
   - S generates a^n (BC)^n
   - CB → BC reorders B's and C's
   - aB → ab, bB → bb convert B's to b's
   - bC → bc, cC → cc convert C's to c's
   
   Result: a^n b^n c^n

2. L = ww (w ∈ {a,b}*)
   CSG exists, but more complex.

3. L = { a^i b^j c^k | i < j < k }
   CSG exists.
""")

# CSG IN CODE
print("=== CSG Implementation ===")

class CSG:
    """A simple context-sensitive grammar."""
    def __init__(self, start, rules):
        self.start = start
        # rules: list of (lhs, rhs) where lhs and rhs are strings
        self.rules = rules
    
    def derive(self, string, max_steps=10000):
        """Check if string can be derived (bounded BFS)."""
        from collections import deque
        
        queue = deque([(self.start, 0)])
        visited = set()
        
        for _ in range(max_steps):
            if not queue:
                break
            current, depth = queue.popleft()
            
            if current == string:
                return True
            
            if current in visited:
                continue
            visited.add(current)
            
            if len(current) > len(string) + 2:
                continue
            
            # Try all rules at all positions
            for lhs, rhs in self.rules:
                for i in range(len(current) - len(lhs) + 1):
                    if current[i:i+len(lhs)] == lhs:
                        new = current[:i] + rhs + current[i+len(lhs):]
                        if len(new) <= len(string) + 2:
                            queue.append((new, depth + 1))
        
        return False


# Example: a^n b^n c^n (simplified grammar)
print("CSG for a^n b^n c^n:")
print("""
  S → aSBC | aBC
  CB → BC
  aB → ab
  bB → bb
  bC → bc
  cC → cc
""")

csg_anbncn = CSG('S', [
    ('S', 'aBC'),
    ('S', 'aSBC'),
    ('CB', 'BC'),
    ('aB', 'ab'),
    ('bB', 'bb'),
    ('bC', 'bc'),
    ('cC', 'cc'),
])

print("Testing (limited steps):")
for w in ['abc', 'aabbcc']:
    result = csg_anbncn.derive(w, max_steps=50000)
    print(f"  '{w}' → {'✓' if result else '✗ (may need more steps)'}")

# DERIVATION EXAMPLE
print("""
=== Derivation Example: aabbcc ===

Start: S

Step 1: S → aSBC
  aSBC

Step 2: S → aBC
  aaBCBC

Step 3: CB → BC
  aaBBCC

Step 4: aB → ab
  aabBCC

Step 5: bB → bb
  aabbCC

Step 6: bC → bc
  aabbcC

Step 7: cC → cc
  aabbcc

Result: aabbcc ✓

=== How It Works ===

1. S generates a^n (BC)^n
   S → aSBC → aaSBCBC → ... → a^n (BC)^n

2. CB → BC reorders:
   a^n (BC)^n → a^n B^n C^n

3. aB → ab, bB → bb:
   Convert B's to b's

4. bC → bc, cC → cc:
   Convert C's to c's

Result: a^n b^n c^n

The context-sensitive rules (CB → BC)
are essential for reordering.
Without them, we couldn't match the counts.
""")

# PROPERTIES OF CSGs
print("""
=== Properties of CSGs ===

1. LENGTH NON-DECREASING
   |RHS| ≥ |LHS| for all rules.
   (Except S → ε if allowed.)

2. CONTEXT MATTERS
   Rules depend on surrounding symbols.
   Can't replace A arbitrarily.

3. EQUIVALENT TO NON-CONTRACTING
   Any non-contracting grammar is a CSG.
   Any CSG is non-contracting.

4. EQUIVALENT TO MONOTONIC
   Rules: α → β with |β| ≥ |α|.

5. CLOSED UNDER MOST OPERATIONS
   Union, intersection, complement, etc.

6. MEMBERSHIP DECIDABLE
   But may be expensive (PSPACE).

=== Comparison with CFG ===

CFG: A → α
  - Single nonterminal on left
  - Context-free
  - Stack memory

CSG: αAβ → αγβ
  - Context on left
  - Context-sensitive
  - Linear tape memory

CSG is strictly more powerful:
  - Can count multiple things
  - Can handle ww
  - Can handle a^n b^n c^n

=== Normal Forms ===

CSGs can be converted to:
  - Length-preserving grammars
    (All rules have |RHS| = |LHS|)
  - Kuroda normal form
    (Specific rule forms)

No simple normal form like CNF/GNF for CFGs.
""")

# SUMMARY
print("""
=== Summary ===

Context-Sensitive Grammar:
  Rules: αAβ → αγβ
  Length non-decreasing
  Context matters

Key properties:
  - |RHS| ≥ |LHS| (except S → ε)
  - Equivalent to non-contracting grammars
  - Generate CSLs

Examples:
  - a^n b^n c^n
  - ww
  - a^i b^j c^k (i < j < k)

Comparison:
  CFG: A → α (context-free)
  CSG: αAβ → αγβ (context-sensitive)

Key insight:
  CSGs add CONTEXT to CFGs.
  This allows:
    - Counting multiple things
    - Copying strings
    - More complex patterns
  
  But membership is still decidable.
  CSLs are between CFL and R.E.
""")

🤖 Linear Bounded Automata

🎯 Turing Machines with Bounded Tape

A Linear Bounded Automaton (LBA) is a Turing machine whose tape is limited to the length of the input (or a linear function of it). This restriction makes membership decidable while still allowing more power than a PDA.

LBA Features

Tape: Linear in input length. Read/Write: Can modify tape. Head: Can move both ways. Deterministic: Can be deterministic or not. Membership: Decidable (PSPACE). Equivalent: To CSGs.

📏 Linear tape↔️ Two-way head✅ Decidable🔄 CSG equivalent

# Linear Bounded Automata
print("=" * 60)
print("LINEAR BOUNDED AUTOMATA (LBA)")
print("=" * 60)

print("""
=== Definition ===

A LINEAR BOUNDED AUTOMATON (LBA) is a Turing machine with:
  - Finite state control
  - Input tape (read-only)
  - Work tape (read/write, length = O(n))

The work tape is BOUNDED:
  - Length is linear in input length
  - Usually exactly |input| + constant
  - Can't use more space than that

=== Formal Definition ===

An LBA is an 8-tuple:
  M = (Q, Σ, Γ, δ, q0, q_accept, q_reject, ◁)

where:
  Q: finite set of states
  Σ: input alphabet
  Γ: tape alphabet (Σ ⊆ Γ)
  δ: Q × Γ → Q × Γ × {L, R}
  q0: start state
  q_accept, q_reject: accept/reject states
  ◁: left end marker (optional)

Key restriction:
  Tape head can't move past the bounds:
    - Left end (position 0)
    - Right end (position n)
  The tape is "bounded" by the input.

=== Why "Linear Bounded"? ===

The tape length is LINEAR in the input:
  |tape| = O(|input|)

For input of length n:
  Tape has n cells (or cn for some constant c)

The machine can't use more space.
This is the key restriction.

=== The Bound ===

Strictly: |tape| = |input| + 2 (for end markers)
Or: |tape| = c · |input| for some constant c

Both definitions are equivalent.

=== LBA vs TM ===

LBA:
  - Tape bounded by input
  - Membership decidable
  - More powerful than PDA
  - Less powerful than TM

TM:
  - Tape infinite
  - Membership undecidable
  - Most powerful model
  - Can compute anything

The bound makes the difference!

=== LBA vs PDA ===

LBA:
  - Tape: random access (can move both ways)
  - More powerful than PDA
  - Can handle a^n b^n c^n
  - Can handle ww

PDA:
  - Stack: LIFO access only
  - Less powerful than LBA
  - Can't handle a^n b^n c^n
  - Can't handle ww

The tape gives more power than the stack.

=== Configurations ===

An LBA configuration is:
  (q, tape, head_position)

where:
  q ∈ Q
  tape ∈ Γ* (length ≤ n + constant)
  head_position ∈ [0, |tape|)

Number of configurations:
  |Q| × |Γ|^(n+1) × (n+1) = O(|Q| × |Γ|^n × n)

This is FINITE (for fixed n)!
So we can decide membership by exhaustive search.

=== Determinism ===

LBAs can be:
  - Deterministic (DLBA)
  - Nondeterministic (NLBA)

Question: Are they equivalent?
  - For TMs: Yes (simulate NTM on DTM)
  - For LBAs: OPEN PROBLEM!
  
  It's unknown whether DLBA = NLBA.
  Most believe they're different.
  
  This is a famous open problem.
""")

# LBA IN CODE
print("=== LBA Implementation ===")

class LBA:
    """A simple Linear Bounded Automaton."""
    def __init__(self, transitions, q0, q_accept, q_reject, blank='_'):
        self.delta = transitions
        self.q0 = q0
        self.q_accept = q_accept
        self.q_reject = q_reject
        self.blank = blank
    
    def run(self, input_string, max_steps=100000, verbose=False):
        """Run LBA on input. Tape bounded by input length."""
        n = len(input_string)
        # Tape: input + one blank on each side (bounded)
        tape = [self.blank] + list(input_string) + [self.blank]
        head = 1  # Start at first input symbol
        state = self.q0
        steps = 0
        
        if verbose:
            print(f"  Initial: tape={''.join(tape)}, head={head}, state={state}")
        
        while steps < max_steps:
            if state == self.q_accept:
                return True, steps
            if state == self.q_reject:
                return False, steps
            
            symbol = tape[head]
            
            if (state, symbol) not in self.delta:
                return False, steps
            
            next_state, write_symbol, direction = self.delta[(state, symbol)]
            tape[head] = write_symbol
            
            # Move head (bounded by tape length)
            if direction == 'R':
                if head < len(tape) - 1:
                    head += 1
                # If at right end, stay (or reject)
            elif direction == 'L':
                if head > 0:
                    head -= 1
                # If at left end, stay (or reject)
            
            state = next_state
            steps += 1
            
            if verbose and steps <= 20:
                tape_str = ''.join(tape)
                marker = ' ' * head + '^'
                print(f"  Step {steps}: tape={tape_str}, head={head}, state={state}")
                print(f"           {marker}")
        
        return False, steps


# Example: LBA for a^n b^n c^n
# Strategy: Use tape to mark and match
print("LBA for a^n b^n c^n:")
print("""
Strategy:
  1. Scan right, find first 'a', mark it 'X'
  2. Scan right, find first 'b', mark it 'Y'
  3. Scan right, find first 'c', mark it 'Z'
  4. Scan left to find next 'a'
  5. Repeat
  6. Accept if all matched

This uses only the input tape (bounded).
""")

# Simplified LBA for a^n b^n c^n
# (A full implementation would be complex)
lba_anbncn = LBA(
    transitions={
        # State q0: find next 'a' to mark
        ('q0', 'a'): ('q1', 'X', 'R'),
        ('q0', 'Y'): ('q0', 'Y', 'R'),
        ('q0', 'Z'): ('q_accept', 'Z', 'R'),
        
        # State q1: skip a's and Y's, find 'b'
        ('q1', 'a'): ('q1', 'a', 'R'),
        ('q1', 'Y'): ('q1', 'Y', 'R'),
        ('q1', 'b'): ('q2', 'Y', 'R'),
        
        # State q2: skip b's and Z's, find 'c'
        ('q2', 'b'): ('q2', 'b', 'R'),
        ('q2', 'Z'): ('q2', 'Z', 'R'),
        ('q2', 'c'): ('q3', 'Z', 'L'),
        
        # State q3: go back to find next 'a'
        ('q3', 'a'): ('q3', 'a', 'L'),
        ('q3', 'b'): ('q3', 'b', 'L'),
        ('q3', 'c'): ('q3', 'c', 'L'),
        ('q3', 'X'): ('q0', 'X', 'R'),
        ('q3', 'Y'): ('q3', 'Y', 'L'),
        ('q3', 'Z'): ('q3', 'Z', 'L'),
    },
    q0='q0',
    q_accept='q_accept',
    q_reject='q_reject',
    blank='_'
)

print("Testing LBA for a^n b^n c^n:")
for w in ['', 'abc', 'aabbcc', 'aaabbbccc', 'ab', 'aabbc']:
    accepted, steps = lba_anbncn.run(w, max_steps=1000)
    result = "✓ ACCEPT" if accepted else "✗ REJECT"
    print(f"  '{w}' → {result} ({steps} steps)")

# Trace
print("\nTrace for 'aabbcc':")
lba_anbncn.run('aabbcc', max_steps=100, verbose=True)

# CONFIGURATION COUNT
print("""
=== Why Membership is Decidable ===

For input of length n, an LBA has:
  - |Q| states
  - |Γ|^(n+1) possible tape contents
  - n+1 possible head positions

Total configurations:
  |Q| × |Γ|^(n+1) × (n+1)

This is FINITE!

So:
  - If the LBA accepts, it does so within
    |Q| × |Γ|^(n+1) × (n+1) steps
  - If it hasn't accepted by then, it never will
  - We can simulate for that many steps
  - If it accepts: accept
  - If not: reject

This is a DECISION PROCEDURE!
Membership is decidable.

=== Complexity ===

The number of configurations is exponential in n:
  |Q| × |Γ|^(n+1) × (n+1) = O(2^n)

So the algorithm is exponential time.
But it uses polynomial space (O(n)).

So membership is in PSPACE.
In fact, it's PSPACE-complete!

=== PSPACE-Completeness ===

The membership problem for LBAs is PSPACE-complete.

This means:
  - It's in PSPACE
  - Every PSPACE problem reduces to it
  - It's among the hardest problems in PSPACE

So LBA membership is:
  - Decidable
  - But expensive (PSPACE-complete)
""")

# SUMMARY
print("""
=== Summary ===

Linear Bounded Automaton:
  - Turing machine with tape bounded by input
  - Tape length = O(n)
  - More powerful than PDA
  - Less powerful than TM

Key properties:
  - Membership decidable (PSPACE)
  - Emptiness undecidable
  - Equivalence undecidable
  - Deterministic vs nondeterministic: OPEN

Configurations:
  |Q| × |Γ|^(n+1) × (n+1) = finite
  So membership can be decided by simulation.

Complexity:
  - Membership: PSPACE-complete
  - Exponential time, polynomial space

Key insight:
  Bounding the tape makes membership decidable.
  But it's still expensive.
  LBA is the machine for CSLs.
""")

🎯 Classic Examples

🎯 Context-Sensitive Languages

These languages are context-sensitive but not context-free. They demonstrate the extra power of CSGs and LBAs.

Classic CSL Examples

aⁿbⁿcⁿ: Three-way counting. ww: Copying. aⁱb^jc^k, i<j<k: Two inequalities. a^n²: Quadratic. Primes: Number theory. ww^R: Palindrome (this is CFL).

🔢 Triple count📋 Copying📊 Inequalities🔢 Squares

# Classic CSL Examples
print("=" * 60)
print("CLASSIC CONTEXT-SENSITIVE LANGUAGES")
print("=" * 60)

# 1. a^n b^n c^n
print("""
=== 1. L = { aⁿbⁿcⁿ | n ≥ 0 } ===

STATUS: CSL, NOT CFL

CSG:
  S → aSBC | aBC
  CB → BC
  aB → ab
  bB → bb
  bC → bc
  cC → cc

How it works:
  1. S generates a^n (BC)^n
  2. CB → BC reorders to a^n B^n C^n
  3. Convert B's to b's, C's to c's
  4. Result: a^n b^n c^n

LBA:
  Strategy: match a's, b's, c's by marking
  1. Mark first a, first b, first c
  2. Go back, repeat
  3. Accept if all matched

NOT CFL:
  Proof: CFL pumping lemma
  Choose w = a^p b^p c^p
  Pumping breaks the balance
  Contradiction. ∎
""")

# 2. ww
print("""
=== 2. L = { ww | w ∈ {a,b}* } ===

STATUS: CSL, NOT CFL

CSG exists (complex).

LBA:
  Strategy: match first half with second half
  1. Find middle (or use markers)
  2. Match w[i] with w[i + n/2]
  3. Accept if all match

NOT CFL:
  Proof: CFL pumping lemma
  Choose w = a^p b^p a^p b^p
  Pumping breaks the ww structure
  Contradiction. ∎

=== 3. L = { aⁱbʲcᵏ | i < j < k } ===

STATUS: CSL, NOT CFL

LBA:
  Strategy: verify the inequalities
  1. Count a's, b's, c's (using tape)
  2. Check i < j and j < k
  3. Accept if both hold

NOT CFL:
  Proof: CFL pumping lemma (complex)
  Or: Intersection with a*b*c* gives a^i b^j c^k
  which is known not CFL.

=== 4. L = { aⁿ² | n ≥ 0 } ===

STATUS: CSL, NOT CFL

LBA:
  Strategy: check if length is a perfect square
  1. Count length n
  2. Check if n = k² for some k
  3. Accept if perfect square

NOT CFL:
  Proof: CFL pumping lemma
  Squares have gaps that grow
  Pumping can't preserve square property
  Contradiction. ∎
""")

# 5. MORE EXAMPLES
print("""
=== 5. L = { aⁿ | n is prime } ===

STATUS: CSL, NOT CFL

LBA:
  Strategy: check primality
  1. Count n (length of input)
  2. Check if n is prime
  3. Accept if prime

NOT CFL:
  Proof: CFL pumping lemma (complex)
  Primes have no simple pattern
  Pumping can't preserve primality

=== 6. L = { wcw | w ∈ {a,b}* } ===

STATUS: CSL, NOT CFL

LBA:
  Strategy: match w before and after c
  1. Find c (middle marker)
  2. Match left part with right part
  3. Accept if all match

NOT CFL:
  Proof: Similar to ww
  c acts as a separator
  Still requires copying

=== 7. L = { aⁱbⁱcⁱ | i ≥ 0 } ===

Same as a^n b^n c^n.

=== 8. L = { aⁱbⁱcⁱdⁱ | i ≥ 0 } ===

STATUS: CSL

Four-way counting.
Still context-sensitive (one tape suffices).

=== 9. L = { w | w has equal a's, b's, c's } ===

STATUS: CSL, NOT CFL

LBA:
  Strategy: count each symbol, compare
  1. Count a's, b's, c's
  2. Check all equal
  3. Accept if equal

NOT CFL:
  Requires 3-way counting
  CFL can only do 1 counter
""")

# COMPARISON TABLE
print("=== Comparison Table ===")
print(f"{'Language':<30} {'CSL?':<10} {'CFL?':<10} {'Regular?':<10}")
print("-" * 60)
print(f"{'aⁿbⁿ':<30} {'Yes':<10} {'Yes':<10} {'No':<10}")
print(f"{'aⁿbⁿcⁿ':<30} {'Yes':<10} {'No':<10} {'No':<10}")
print(f"{'ww':<30} {'Yes':<10} {'No':<10} {'No':<10}")
print(f"{'aⁱbʲcᵏ, i 0:
                head -= 1
            
            state = ns
            steps += 1
        
        return False, steps


sim = LBASim()
print("LBA for a^n b^n c^n:")
for w in ['', 'abc', 'aabbcc', 'aaabbbccc', 'ab', 'aabbc']:
    accepted, steps = sim.run(w)
    print(f"  '{w}' → {'✓' if accepted else '✗'} ({steps} steps)")

# SUMMARY
print("""
=== Summary ===

Classic CSLs:
  - a^n b^n c^n (three-way counting)
  - ww (copying)
  - a^i b^j c^k (i < j < k)
  - a^n² (squares)
  - a^n (prime)
  - wcw (marked copy)
  - a^i b^i c^i d^i (four-way counting)
  - Equal counts of a, b, c

All are:
  - Context-sensitive (CSG exists)
  - Not context-free (pumping lemma)
  - Recognized by LBAs

Key insight:
  CSLs can count MULTIPLE things.
  CSLs can COPY strings.
  CSLs can handle complex patterns.
  But membership is still decidable.
""")

📊 Properties

🎯 Properties of CSLs

Context-sensitive languages have a rich set of properties, including closure properties and decidability results that distinguish them from both CFLs and recursively enumerable languages.

Key Properties

Closure: Union, intersection, complement. Decidable: Membership (PSPACE). Undecidable: Emptiness, equivalence. Memory: Linear tape. Hierarchy: Between CFL and R.E. Determinism: DLBA vs NLBA open.

🔒 Closed✅ Membership❌ Emptiness📊 Hierarchy

# Properties of Context-Sensitive Languages
print("=" * 60)
print("PROPERTIES OF CONTEXT-SENSITIVE LANGUAGES")
print("=" * 60)

print("""
=== Closure Properties ===

CSLs are CLOSED under:
  ✓ Union
  ✓ Intersection
  ✓ Complement
  ✓ Concatenation
  ✓ Kleene star
  ✓ Reversal
  ✓ Homomorphism
  ✓ Inverse homomorphism
  ✓ Difference
  ✓ Symmetric difference

CSLs are closed under ALMOST EVERYTHING!

This is a key difference from CFLs:
  CFL: NOT closed under intersection, complement
  CSL: Closed under intersection, complement

=== Why This Matters ===

CFLs lose closure under intersection.
CSLs regain it.

Why?
  CFL: one stack (LIFO)
  CSL: linear tape (random access)

The tape allows:
  - Simulating two stacks (for intersection)
  - Deterministic complementation
  - More robust closure properties

=== Decidability ===

Membership:
  ✓ Decidable (PSPACE-complete)
  - Simulate LBA
  - Finite configurations
  - Always halts

Emptiness:
  ✗ Undecidable
  - Given CSG G, is L(G) = ∅?
  - Related to halting problem
  - No algorithm

Equivalence:
  ✗ Undecidable
  - Given CSGs G1, G2, is L(G1) = L(G2)?
  - No algorithm

Universality:
  ✗ Undecidable
  - Is L(G) = Σ*?
  - No algorithm

Finiteness:
  ✗ Undecidable
  - Is L(G) finite?
  - No algorithm

Inclusion:
  ✗ Undecidable
  - Is L(G1) ⊆ L(G2)?
  - No algorithm

=== The Decidability Landscape ===

Only membership is decidable.
Most other problems are undecidable.

This is because:
  - LBA membership: PSPACE (decidable)
  - LBA emptiness: undecidable
  - CSG equivalence: undecidable

So CSLs are "between" CFL and TM:
  - More decidable than TM
  - Less decidable than CFL
""")

# CLOSURE PROOFS
print("""
=== Closure Proofs ===

UNION (L1 ∪ L2):
  Given CSGs G1, G2:
    - Create new start S
    - Add S → S1 | S2
    - Result: CSG for L1 ∪ L2
  
INTERSECTION (L1 ∩ L2):
  Use product construction on LBAs:
    - States: Q1 × Q2
    - Simulate both LBAs
    - Accept if both accept
    - Result: LBA for L1 ∩ L2

COMPLEMENT (Σ* \ L):
  Given LBA M:
    - Swap accept and reject states
    - Handle "stuck" configurations
    - Result: LBA for complement
  
  (This works for LBAs because they always halt.)

CONCATENATION (L1 · L2):
  - Connect M1's accept to M2's start
  - Use markers for the boundary
  - Result: LBA for L1 · L2

KLEENE STAR (L*):
  - Loop back from accept to start
  - Result: LBA for L*

=== Why Complement Works ===

LBAs always halt (membership is decidable).
So we can:
  1. Run M on input w
  2. If M accepts: reject
  3. If M rejects: accept

This gives the complement.

For CFLs, this doesn't work:
  - PDAs may loop
  - Nondeterminism
  - Complement not always CFL

For LBAs, it works:
  - LBAs halt (on bounded tape)
  - Can swap accept/reject
  - Complement is CSL
""")

# DECIDABILITY PROOFS
print("""
=== Decidability Proofs ===

MEMBERSHIP (decidable):
  Given CSG G and string w:
    1. Convert G to LBA M
    2. Simulate M on w for at most
       |Q| × |Γ|^(n+1) × (n+1) steps
    3. If M accepts, accept
    4. If not, reject
  
  This always halts.
  So membership is decidable.

EMPTINESS (undecidable):
  Given CSG G:
    Is L(G) = ∅?
  
  This is undecidable.
  Proof: Reduce from halting problem.
  (Complex, but standard.)

EQUIVALENCE (undecidable):
  Given CSGs G1, G2:
    Is L(G1) = L(G2)?
  
  Undecidable.
  Proof: Reduce from emptiness.

=== Why Emptiness is Undecidable ===

For CFGs, emptiness is decidable:
  - Check generating symbols
  - Polynomial time

For CSGs, emptiness is undecidable:
  - Grammar can have complex rules
  - Derivation search may not terminate
  - Related to halting problem

This is surprising!
  - CFG emptiness: easy
  - CSG emptiness: impossible

The extra power of CSGs
makes emptiness harder.
""")

# SUMMARY TABLE
print("=== Properties Summary ===")
print(f"{'Property':<30} {'Regular':<12} {'CFL':<12} {'CSL':<12} {'R.E.':<12}")
print("-" * 80)
print(f"{'Membership':<30} {'✓ O(n)':<12} {'✓ O(n³)':<12} {'✓ PSPACE':<12} {'✗':<12}")
print(f"{'Emptiness':<30} {'✓':<12} {'✓':<12} {'✗':<12} {'✗':<12}")
print(f"{'Finiteness':<30} {'✓':<12} {'✓':<12} {'✗':<12} {'✗':<12}")
print(f"{'Equivalence':<30} {'✓':<12} {'✗':<12} {'✗':<12} {'✗':<12}")
print(f"{'Universality':<30} {'✓':<12} {'✗':<12} {'✗':<12} {'✗':<12}")
print(f"{'Intersection':<30} {'✓':<12} {'✗':<12} {'✓':<12} {'✓':<12}")
print(f"{'Complement':<30} {'✓':<12} {'✗':<12} {'✓':<12} {'✗':<12}")
print(f"{'Union':<30} {'✓':<12} {'✓':<12} {'✓':<12} {'✓':<12}")
print(f"{'Concatenation':<30} {'✓':<12} {'✓':<12} {'✓':<12} {'✓':<12}")
print(f"{'Kleene Star':<30} {'✓':<12} {'✓':<12} {'✓':<12} {'✓':<12}")

# SUMMARY
print("""
=== Summary ===

CSL Properties:

CLOSURE:
  ✓ Union, intersection, complement
  ✓ Concatenation, star, reversal
  ✓ Homomorphism, inverse homomorphism
  → Closed under almost everything!

DECIDABILITY:
  ✓ Membership: PSPACE-complete
  ✗ Emptiness: undecidable
  ✗ Equivalence: undecidable
  ✗ Universality: undecidable
  ✗ Finiteness: undecidable
  → Only membership is decidable.

COMPARISON:
  CFL: less closure, more decidable
  CSL: more closure, less decidable
  R.E.: less closure, least decidable

Key insight:
  CSLs are a sweet spot:
    - More powerful than CFL
    - Membership decidable
    - Good closure properties
    - But most other problems undecidable
""")

✅ Decidability

🎯 What Can We Decide About CSLs?

Context-sensitive languages have a mixed decidability profile: membership is decidable (PSPACE-complete), but most other problems are undecidable. This places CSLs between CFLs (more decidable) and R.E. languages (less decidable).

Decidability Results

Membership: Decidable (PSPACE-complete). Emptiness: Undecidable. Equivalence: Undecidable. Universality: Undecidable. Finiteness: Undecidable. Inclusion: Undecidable.

✅ Membership❌ Emptiness❌ EquivalencePSPACE

# Decidability of CSL Problems
print("=" * 60)
print("DECIDABILITY OF CSL PROBLEMS")
print("=" * 60)

print("""
=== Membership ===

Problem: Given CSG G and string w, is w ∈ L(G)?

STATUS: DECIDABLE

Proof:
  1. Convert CSG to LBA.
  2. Simulate LBA on w.
  3. LBA has finitely many configurations:
     |Q| × |Γ|^(n+1) × (n+1)
  4. If LBA accepts within that many steps, accept.
  5. If not, reject.
  
  This always halts.
  So membership is decidable.

COMPLEXITY: PSPACE-complete

=== Why PSPACE? ===

The LBA simulation uses:
  - Polynomial space: O(n)
  - Exponential time: O(2^n)

So membership ∈ PSPACE.

It's PSPACE-complete:
  - Every PSPACE problem reduces to it.
  - It's among the hardest in PSPACE.

=== Emptiness ===

Problem: Given CSG G, is L(G) = ∅?

STATUS: UNDECIDABLE

Proof (sketch):
  Reduce from halting problem.
  Given TM M and input w:
    Construct CSG G such that:
      L(G) = ∅ iff M loops on w
      L(G) ≠ ∅ iff M halts on w
  Then deciding emptiness would decide halting.
  Contradiction.
  So emptiness is undecidable. ∎

=== Equivalence ===

Problem: Given CSGs G1, G2, is L(G1) = L(G2)?

STATUS: UNDECIDABLE

Proof:
  Reduce from emptiness.
  Given CSG G:
    Construct G1 = G
    Construct G2 = CSG for ∅
  Then L(G1) = L(G2) iff L(G) = ∅.
  Deciding equivalence would decide emptiness.
  But emptiness is undecidable.
  So equivalence is undecidable. ∎

=== Universality ===

Problem: Given CSG G, is L(G) = Σ*?

STATUS: UNDECIDABLE

Proof:
  Reduce from emptiness.
  Given CSG G:
    Construct G' for complement of L(G).
  Then L(G) = Σ* iff L(G') = ∅.
  But emptiness is undecidable.
  So universality is undecidable. ∎

=== Finiteness ===

Problem: Given CSG G, is L(G) finite?

STATUS: UNDECIDABLE

Proof:
  Reduce from halting problem (complex).
  Similar to emptiness.

=== Inclusion ===

Problem: Given CSGs G1, G2, is L(G1) ⊆ L(G2)?

STATUS: UNDECIDABLE

Proof:
  L(G1) ⊆ L(G2) iff L(G1) ∩ complement(L(G2)) = ∅.
  Since CSLs are closed under complement and intersection,
  this reduces to emptiness.
  But emptiness is undecidable.
  So inclusion is undecidable. ∎
""")

# COMPARISON TABLE
print("""
=== Decidability Comparison ===

Problem          Regular    CFL       CSL       R.E.
─────────────────────────────────────────────────────
Membership       ✓ O(n)     ✓ O(n³)   ✓ PSPACE  ✗
Emptiness        ✓          ✓         ✗         ✗
Finiteness       ✓          ✓         ✗         ✗
Equivalence      ✓          ✗         ✗         ✗
Universality     ✓          ✗         ✗         ✗
Inclusion        ✓          ✗         ✗         ✗
Intersection     ✓          ✗         ✓         ✓
Complement       ✓          ✗         ✓         ✗

Key observations:
  - Regular: everything decidable
  - CFL: most decidable (except equivalence, etc.)
  - CSL: only membership decidable
  - R.E.: almost nothing decidable

The pattern:
  More power → less decidability
  But CSL is not monotonic:
    - Intersection/complement come back (unlike CFL)
    - But emptiness/equivalence stay undecidable

=== Why This Pattern? ===

Regular:
  - Finite states
  - Simple structure
  - Everything decidable

CFL:
  - Stack memory
  - Nondeterminism
  - Some problems undecidable

CSL:
  - Linear tape
  - More power
  - Only membership decidable
  - But closed under intersection/complement

R.E.:
  - Infinite tape
  - Full power
  - Almost everything undecidable
""")

# PSPACE COMPLETENESS
print("""
=== PSPACE-Completeness ===

Membership for LBAs is PSPACE-complete.

PSPACE = problems solvable in polynomial space.

Known:
  P ⊆ NP ⊆ PSPACE ⊆ EXP

Open:
  P = NP? (probably not)
  NP = PSPACE? (probably not)
  P = PSPACE? (probably not)

PSPACE-complete problems:
  - LBA membership
  - QBF (Quantified Boolean Formula)
  - Generalized geography
  - Many game problems

=== Why Membership is PSPACE ===

LBA uses O(n) space.
Simulation uses:
  - Space: O(n) for tape
  - Time: O(2^n) for exhaustive search

So membership ∈ PSPACE.

PSPACE-completeness means:
  - It's in PSPACE
  - Every PSPACE problem reduces to it
  - It's among the hardest in PSPACE

=== Practical Implications ===

If your problem is PSPACE-complete:
  - Exact solution is expensive
  - But not impossible (unlike undecidable)
  - Use approximation, heuristics, special cases

LBA membership is PSPACE-complete.
So recognizing CSLs can be expensive.
But it's always possible (unlike TM).
""")

# SUMMARY
print("""
=== Summary ===

CSL Decidability:

✓ MEMBERSHIP: Decidable
  - PSPACE-complete
  - Simulate LBA
  - Always halts

✗ EMPTINESS: Undecidable
  - Reduce from halting problem

✗ EQUIVALENCE: Undecidable
  - Reduce from emptiness

✗ UNIVERSALITY: Undecidable
  - Reduce from emptiness

✗ FINITENESS: Undecidable
  - Reduce from halting problem

✗ INCLUSION: Undecidable
  - Reduce from emptiness

Key insight:
  Only membership is decidable for CSLs.
  This places CSLs between CFL (more decidable)
  and R.E. (less decidable).
  
  But CSLs have better closure properties than CFLs.
  This is the trade-off.
""")

🔒 Closure Properties

🎯 What Operations Preserve CSLs?

Context-sensitive languages are closed under almost all standard operations, including union, intersection, complement, concatenation, and Kleene star. This is a key advantage over CFLs.

Closure Properties

Closed under: Union, intersection, complement, concat, star, reversal, homomorphism. Difference: Also closed. Proof: LBA constructions. Contrast: CFLs are NOT closed under ∩ or complement. Key: Linear tape gives more closure.

✅ Union✅ Intersection✅ Complement✅ Concat✅ Star

# Closure Properties of CSLs
print("=" * 60)
print("CLOSURE PROPERTIES OF CSLs")
print("=" * 60)

print("""
=== Operations that PRESERVE CSLs ===

✓ UNION: L1 ∪ L2
  Construction: New start S → S1 | S2

✓ INTERSECTION: L1 ∩ L2
  Construction: Product of LBAs
    - States: Q1 × Q2
    - Simulate both LBAs
    - Accept if both accept

✓ COMPLEMENT: Σ* \ L
  Construction: Swap accept/reject in LBA
    - LBAs always halt
    - So complement is easy

✓ CONCATENATION: L1 · L2
  Construction: Connect M1's accept to M2's start

✓ KLEENE STAR: L*
  Construction: Loop back from accept to start

✓ REVERSAL: L^R
  Construction: Reverse transitions

✓ HOMOMORPHISM: h(L)
  Construction: Apply h to terminals

✓ INVERSE HOMOMORPHISM: h⁻¹(L)
  Construction: More complex, but works

✓ DIFFERENCE: L1 \ L2
  Construction: L1 ∩ complement(L2)

✓ SYMMETRIC DIFFERENCE: L1 △ L2
  Construction: (L1 \ L2) ∪ (L2 \ L1)

=== Key Point ===

CSLs are closed under ALMOST EVERYTHING!

This is a major difference from CFLs:
  CFL: NOT closed under intersection, complement
  CSL: Closed under intersection, complement

=== Why This Works ===

The LBA has a LINEAR TAPE:
  - Random access (unlike stack)
  - Can simulate multiple machines
  - Can deterministically complement
  - Can handle complex constructions

This gives:
  - More closure properties
  - More robustness
  - But also more complexity
""")

# CONSTRUCTION PROOFS
print("""
=== Construction Proofs ===

UNION (L1 ∪ L2):
  Given CSGs G1, G2:
    Create new start S
    Add S → S1 | S2
    Result: CSG for L1 ∪ L2
  
  Given LBAs M1, M2:
    New start state q0
    ε-transitions to M1's start and M2's start
    Accept if either accepts
    Result: LBA for L1 ∪ L2

INTERSECTION (L1 ∩ L2):
  Given LBAs M1, M2:
    New states: Q1 × Q2
    Start: (q0_1, q0_2)
    Transitions: simulate both
    Accept: both accept
    Result: LBA for L1 ∩ L2
  
  This is the PRODUCT CONSTRUCTION.

COMPLEMENT (Σ* \ L):
  Given LBA M:
    Swap q_accept and q_reject
    Handle "stuck" configurations:
      - Add transitions to reject state
    Result: LBA for complement
  
  Works because LBAs always halt.
  (No infinite loops on bounded tape.)

CONCATENATION (L1 · L2):
  Given LBAs M1, M2:
    - Run M1 on input
    - When M1 accepts, run M2 on rest
    - Use nondeterminism to guess split point
    - Result: LBA for L1 · L2

KLEENE STAR (L*):
  Given LBA M:
    - Run M on segments
    - Loop back after each accept
    - Use nondeterminism to guess segment boundaries
    - Result: LBA for L*
""")

# COMPARISON TABLE
print("=== Closure Comparison ===")
print(f"{'Operation':<25} {'Regular':<12} {'CFL':<12} {'CSL':<12} {'R.E.':<12}")
print("-" * 75)
print(f"{'Union':<25} {'✓':<12} {'✓':<12} {'✓':<12} {'✓':<12}")
print(f"{'Intersection':<25} {'✓':<12} {'✗':<12} {'✓':<12} {'✓':<12}")
print(f"{'Complement':<25} {'✓':<12} {'✗':<12} {'✓':<12} {'✗':<12}")
print(f"{'Difference':<25} {'✓':<12} {'✗':<12} {'✓':<12} {'✗':<12}")
print(f"{'Concatenation':<25} {'✓':<12} {'✓':<12} {'✓':<12} {'✓':<12}")
print(f"{'Kleene Star':<25} {'✓':<12} {'✓':<12} {'✓':<12} {'✓':<12}")
print(f"{'Reversal':<25} {'✓':<12} {'✓':<12} {'✓':<12} {'✓':<12}")
print(f"{'Homomorphism':<25} {'✓':<12} {'✓':<12} {'✓':<12} {'✓':<12}")
print(f"{'Inverse Homomorphism':<25} {'✓':<12} {'✓':<12} {'✓':<12} {'✓':<12}")
print(f"{'∩ Regular':<25} {'✓':<12} {'✓':<12} {'✓':<12} {'✓':<12}")

print("""
=== The Closure Landscape ===

Regular:  Closed under everything.
CFL:      Closed under union, concat, star.
          NOT closed under intersection, complement.
CSL:      Closed under almost everything.
          INCLUDING intersection and complement!
R.E.:     Closed under union, intersection.
          NOT closed under complement.

Key observations:
  - CSL is more "closed" than CFL
  - CSL regains intersection and complement
  - R.E. loses complement (compared to CSL)

This is a non-monotonic pattern:
  Regular → CFL: lose some closure
  CFL → CSL: regain some closure
  CSL → R.E.: lose complement again

=== Why Does This Happen? ===

Regular:
  Finite states → simple constructions

CFL:
  Stack (LIFO) → can't easily intersect
  Nondeterminism → hard to complement

CSL:
  Linear tape → can simulate intersection
  Always halts → easy to complement

R.E.:
  Infinite tape → can simulate anything
  May not halt → hard to complement
""")

# SUMMARY
print("""
=== Summary ===

CSLs are closed under:

✓ Union
✓ Intersection
✓ Complement
✓ Difference
✓ Symmetric difference
✓ Concatenation
✓ Kleene star
✓ Reversal
✓ Homomorphism
✓ Inverse homomorphism
✓ Intersection with regular

Almost everything!

Key insight:
  CSLs have BETTER closure properties than CFLs.
  This is because LBAs have more power
  (linear tape vs stack).
  
  But this extra power comes at a cost:
  - Membership is PSPACE-complete (expensive)
  - Emptiness is undecidable
  - Equivalence is undecidable

Trade-off:
  More closure vs less decidability.
""")

🏛️ Position in Hierarchy

🎯 Where CSLs Fit

Context-sensitive languages sit at Type 1 in the Chomsky hierarchy, strictly between context-free languages (Type 2) and recursively enumerable languages (Type 0).

Hierarchy Position

Contains: All CFLs. Contained in: All R.E. languages. Strict: Both inclusions are strict. Separating: aⁿbⁿcⁿ (CSL not CFL). Separating: HALT (R.E. not CSL). Grammar: Type 1. Machine: LBA.

📗 Contains CFL🖥️ In R.E.📏 Strict both🎯 Type 1

# Position in the Chomsky Hierarchy
print("=" * 60)
print("POSITION IN THE CHOMSKY HIERARCHY")
print("=" * 60)

print("""
=== The Hierarchy ===

  Type 3: Regular
    ⊊
  Type 2: Context-Free
    ⊊
  Type 1: Context-Sensitive  ← WE ARE HERE
    ⊊
  Type 0: Recursively Enumerable

CSLs sit between CFL and R.E.

=== Strict Inclusions ===

CFL ⊊ CSL:
  Proof: L = { aⁿbⁿcⁿ } is CSL but not CFL.
    - CSG exists
    - CFL pumping lemma shows not CFL

CSL ⊊ R.E.:
  Proof: L = HALT is R.E. but not CSL.
    - HALT is r.e. (simulate)
    - CSL membership is decidable
    - But HALT membership is undecidable
    - So HALT is not CSL

Both inclusions are STRICT.

=== Visual ===

  ┌─────────────────────────────────────────────┐
  │ Type 0: Recursively Enumerable              │
  │ (Turing machines)                           │
  │                                             │
  │   ┌─────────────────────────────────────┐   │
  │   │ Type 1: Context-Sensitive           │   │
  │   │ (Linear bounded automata)           │   │
  │   │                                     │   │
  │   │   ┌─────────────────────────────┐   │   │
  │   │   │ Type 2: Context-Free        │   │   │
  │   │   │ (Pushdown automata)         │   │   │
  │   │   │                             │   │   │
  │   │   │   ┌─────────────────────┐   │   │   │
  │   │   │   │ Type 3: Regular     │   │   │   │
  │   │   │   │ (Finite automata)   │   │   │   │
  │   │   │   └─────────────────────┘   │   │   │
  │   │   └─────────────────────────────┘   │   │
  │   └─────────────────────────────────────┘   │
  └─────────────────────────────────────────────┘

=== Grammar-Machine Correspondence ===

Type 3: A → aB | a       ↔  Finite automaton
Type 2: A → α            ↔  Pushdown automaton
Type 1: αAβ → αγβ        ↔  Linear bounded automaton
Type 0: α → β            ↔  Turing machine

Each grammar type matches a machine type.

=== Language Class Inclusions ===

Regular ⊊ CFL ⊊ CSL ⊊ R.E.

Examples separating each level:

Regular vs CFL:
  L = { aⁿbⁿ } is CFL but not regular.

CFL vs CSL:
  L = { aⁿbⁿcⁿ } is CSL but not CFL.

CSL vs R.E.:
  L = HALT is R.E. but not CSL.
""")

# COMPARISON TABLE
print("=== Comprehensive Comparison ===")
print(f"{'Aspect':<25} {'Type 3':<20} {'Type 2':<20} {'Type 1':<20} {'Type 0':<20}")
print("-" * 105)
print(f"{'Grammar':<25} {'Regular':<20} {'Context-Free':<20} {'Context-Sens.':<20} {'Unrestricted':<20}")
print(f"{'Rule form':<25} {'A→aB|a':<20} {'A→α':<20} {'αAβ→αγβ':<20} {'α→β':<20}")
print(f"{'Machine':<25} {'Finite':<20} {'Pushdown':<20} {'Linear bounded':<20} {'Turing':<20}")
print(f"{'Memory':<25} {'None':<20} {'Stack':<20} {'Linear tape':<20} {'Infinite tape':<20}")
print(f"{'Example':<25} {'a*b*':<20} {'aⁿbⁿ':<20} {'aⁿbⁿcⁿ':<20} {'HALT':<20}")
print(f"{'Membership':<25} {'O(n)':<20} {'O(n³)':<20} {'PSPACE':<20} {'Undecidable':<20}")
print(f"{'Emptiness':<25} {'✓':<20} {'✓':<20} {'✗':<20} {'✗':<20}")
print(f"{'Equivalence':<25} {'✓':<20} {'✗':<20} {'✗':<20} {'✗':<20}")
print(f"{'Closure ∩':<25} {'✓':<20} {'✗':<20} {'✓':<20} {'✓':<20}")
print(f"{'Closure ¬':<25} {'✓':<20} {'✗':<20} {'✓':<20} {'✗':<20}")
print(f"{'Practical':<25} {'Lexers':<20} {'Parsers':<20} {'Some NLP':<20} {'General':<20}")

# PRACTICAL SIGNIFICANCE
print("""
=== Practical Significance ===

CSLs are less practical than CFLs or Regular:
  - Parsing is expensive (PSPACE)
  - Most problems undecidable
  - Grammars are hard to design

But CSLs are important for:
  1. NATURAL LANGUAGE
     Some linguistic phenomena are context-sensitive.
     Cross-serial dependencies in Dutch.
     
  2. THEORETICAL COMPLETENESS
     Fill the gap between CFL and R.E.
     
  3. UNDERSTANDING COMPUTATION
     Show the trade-off between power and decidability.
     
  4. SOME APPLICATIONS
     Type checking (partially)
     Protocol verification
     Bioinformatics

=== The Practical Pipeline ===

  Source → Lexer (Type 3) → Tokens
         → Parser (Type 2) → AST
         → Semantic (Type 1/0) → IR
         → Code Gen (Type 0) → Machine code

Each phase uses the appropriate level.
Type 1 is used for some semantic analysis.

=== Why Not Use Type 1 Everywhere? ===

Because:
  - Parsing Type 1 is PSPACE (expensive)
  - Most problems undecidable
  - Grammars are hard to write
  - Type 2 is sufficient for syntax

So we use:
  - Type 3: Tokenization
  - Type 2: Syntax
  - Type 1/0: Semantics
  - Type 0: Computation

This is the practical sweet spot.
""")

# SUMMARY
print("""
=== Summary ===

CSL in the Hierarchy:

Position:
  Between CFL (Type 2) and R.E. (Type 0)
  Type 1 in the Chomsky hierarchy

Inclusions:
  CFL ⊊ CSL ⊊ R.E.
  Both strict.

Separating examples:
  CFL vs CSL: a^n b^n c^n
  CSL vs R.E.: HALT

Grammar: Context-sensitive
Machine: Linear bounded automaton
Memory: Linear tape

Key properties:
  - Membership: PSPACE-complete
  - Emptiness: undecidable
  - Closed under almost everything
  - More powerful than CFL
  - Less powerful than TM

Key insight:
  CSLs are the "middle child" of the hierarchy.
  More power than CFL, less than TM.
  Membership decidable, but expensive.
  Good closure properties.
  
  They complete the hierarchy and
  fill the gap between CFL and R.E.
""")

💼 Applications

🎯 CSLs in the Real World

While context-sensitive languages are less common in practice than regular or context-free languages, they do appear in natural language processing, bioinformatics, and some verification tasks.

Application Areas

Natural language: Cross-serial dependencies. Bioinformatics: RNA structure, protein folding. Verification: Some protocol properties. Type systems: Some advanced type checking. Theory: Completing the hierarchy. Research: Understanding computation limits.

🗣️ NLP🧬 Bio🔬 Research📘 Theory

# Applications of CSLs
print("=" * 60)
print("APPLICATIONS OF CONTEXT-SENSITIVE LANGUAGES")
print("=" * 60)

# 1. NATURAL LANGUAGE
print("""
=== 1. Natural Language ===

Some linguistic phenomena are context-sensitive:

CROSS-SERIAL DEPENDENCIES (Dutch):
  ... dat Jan Piet Marie zag helpen zwemmen
  ... that Jan Piet Marie saw help swim
  
  The verbs "zag", "helpen", "zwemmen"
  match with "Jan", "Piet", "Marie" in order.
  
  This is cross-serial, not nested.
  Context-free grammars can't handle this.
  Context-sensitive grammars can.

AGREEMENT PATTERNS:
  Some languages have agreement that
  depends on context.
  
  Example: Swahili verb agreement
  Context-sensitive in some analyses.

WORD ORDER:
  Some languages have word order
  that depends on context.
  
  Example: German verb placement
  Context-sensitive in some analyses.

=== The Debate ===

Is natural language:
  - Context-free? (Chomsky's original view)
  - Context-sensitive? (Some linguists)
  - Mildly context-sensitive? (Middle ground)
  - Something else?

Most linguists now believe:
  - Natural language is NOT context-free
  - It's at least mildly context-sensitive
  - Maybe full context-sensitive

This affects NLP algorithms.
""")

# 2. BIOINFORMATICS
print("""
=== 2. Bioinformatics ===

RNA SECONDARY STRUCTURE:
  RNA folds into shapes.
  Base pairs: A-U, G-C.
  Nested structure = context-free.
  Pseudoknots = context-sensitive!

  Pseudoknots:
    - Not nested
    - Cross-serial interactions
    - Context-sensitive

  Grammar for RNA with pseudoknots:
    S → a S u | c S g | g S c | u S a
      | S S | a S u S | ...
    
    More complex than CFG.
    Needs context-sensitive power.

PROTEIN FOLDING:
  Protein structure is complex.
  Some aspects are context-sensitive.
  Full folding is NP-hard (maybe harder).

DNA COMPUTING:
  DNA can compute.
  Adleman (1994): Hamiltonian path.
  Context-sensitive operations possible.

=== 3. VERIFICATION ===

PROTOCOL VERIFICATION:
  Some protocol properties are context-sensitive.
  Example: matching requests with responses.
  Example: session tracking.

TYPE CHECKING:
  Some type systems need context-sensitive power.
  Example: dependent types.
  Example: linear types.

PROGRAM ANALYSIS:
  Some analyses are context-sensitive.
  Example: interprocedural analysis.
  Example: alias analysis.
""")

# 4. THEORETICAL IMPORTANCE
print("""
=== 4. Theoretical Importance ===

CSLs complete the Chomsky hierarchy:

  Regular ⊊ CFL ⊊ CSL ⊊ R.E.

Without CSLs, there would be a gap:
  - Between CFL and R.E.
  - Some languages wouldn't fit
  - The hierarchy would be incomplete

CSLs also show:
  - Membership can be decidable
    even for powerful models
  - Closure properties can be regained
    at higher levels
  - Power vs decidability trade-off

=== 5. DECIDABILITY BOUNDARY ===

CSLs are at the boundary:
  - Membership: decidable
  - Emptiness: undecidable

This is a sharp transition:
  - Below: more decidable
  - Above: less decidable

Understanding this boundary
is theoretically important.

=== 6. OPEN PROBLEMS ===

1. DLBA vs NLBA
   Are deterministic and nondeterministic
   LBAs equivalent?
   OPEN PROBLEM!
   
   Most believe: No.
   But no proof.

2. Is natural language context-sensitive?
   Still debated.
   Affects NLP.

3. CSL parsing complexity
   PSPACE-complete, but can we do better
   for specific CSLs?
   
   Yes, for many practical cases.

4. CSL and complexity classes
   CSL membership = PSPACE
   What about subclasses?
""")

# 7. SUMMARY TABLE
print("=== Application Summary ===")
print(f"{'Domain':<25} {'Use Case':<30} {'CSL Role':<25}")
print("-" * 80)
print(f"{'NLP':<25} {'Cross-serial deps':<30} {'Context-sensitive':<25}")
print(f"{'Bioinformatics':<25} {'RNA pseudoknots':<30} {'Context-sensitive':<25}")
print(f"{'Verification':<25} {'Protocol analysis':<30} {'Matching requests':<25}")
print(f"{'Type systems':<25} {'Advanced types':<30} {'Dependent types':<25}")
print(f"{'Theory':<25} {'Hierarchy completion':<30} {'Type 1':<25}")
print(f"{'Research':<25} {'DLBA vs NLBA':<30} {'Open problem':<25}")

# 8. CASE STUDY: RNA PSEUDOKNOTS
print("""
=== Case Study: RNA Pseudoknots ===

RNA secondary structure:
  - Stems: base-paired regions
  - Loops: unpaired regions
  - Pseudoknots: crossing base pairs

Without pseudoknots:
  Structure is nested.
  Context-free grammar:
    S → a S u | c S g | g S c | u S a | S S | ε

With pseudoknots:
  Structure is crossing.
  NOT context-free.
  Needs context-sensitive grammar:
    S → a S u | c S g | g S c | u S a
      | a S u S | c S g S | ...
    More complex rules.

Why it matters:
  - Pseudoknots are biologically important
  - They affect RNA function
  - CFG can't model them
  - CSG can!

Tools:
  - Pfold (CFG-based)
  - ILM (CSG-based)
  - HotKnots (heuristic)

This is a real application of CSLs.
""")

# 9. TAKEAWAYS
print("""
=== Practical Takeaways ===

1. CSLs ARE RARE IN PRACTICE
   - Less common than CFL or regular
   - But they do appear
   - Know when they're needed

2. NATURAL LANGUAGE
   - Some phenomena are context-sensitive
   - Affects NLP algorithms
   - Still debated

3. BIOINFORMATICS
   - RNA pseudoknots
   - Some protein structures
   - Real applications

4. VERIFICATION
   - Some protocol properties
   - Some type systems
   - Some program analyses

5. THEORY
   - Complete the hierarchy
   - Understand decidability boundary
   - Open problems (DLBA vs NLBA)

6. PRACTICAL ADVICE
   - Use CFL when possible
   - Use CSL when needed
   - Be aware of complexity (PSPACE)

Key insight:
  CSLs are the "middle child" of the hierarchy.
  Less practical than CFL, but more powerful.
  Used in specialized applications.
  Theoretically important.
""")

🚀 Advanced Topics

🎯 Beyond Basic CSLs

Context-sensitive languages connect to many advanced topics: mildly context-sensitive languages, open problems, quantum computing, and the limits of computation.

Advanced Directions

Mildly CS: Between CFL and CSL. DLBA vs NLBA: Open problem. Quantum: Quantum CSLs. Complexity: PSPACE, etc. Natural language: Context-sensitivity. Bio: RNA, proteins.

🌳 Mildly CS❓ Open problems⚛️ Quantum🧬 Bio

# Advanced Topics in CSLs
print("=" * 60)
print("ADVANCED TOPICS")
print("=" * 60)

# 1. MILDLY CONTEXT-SENSITIVE
print("""
=== 1. Mildly Context-Sensitive Languages ===

Between CFL and CSL:

Properties:
  - More powerful than CFL
  - Less powerful than CSL
  - Parseable in polynomial time
  - Good for natural language

Formalisms:
  - Tree Adjoining Grammars (TAG)
  - Head Grammars (HG)
  - Linear Indexed Grammars (LIG)
  - Combinatory Categorial Grammars (CCG)
  - Multiple Context-Free Grammars (MCFG)

All are weakly equivalent:
  They generate the same class of languages.

=== Why "Mildly"? ===

Mildly context-sensitive languages:
  - Can handle cross-serial dependencies
  - Can handle some natural language phenomena
  - Still efficiently parseable (O(n^6) or better)
  - Not as complex as full CSL

Used in:
  - Computational linguistics
  - Natural language parsing
  - Treebanks

=== Example: Tree Adjoining Grammars ===

TAG combines tree fragments:
  - Substitution: replace leaf with tree
  - Adjunction: insert tree into tree

Generates:
  - All CFLs
  - Some non-CFLs (a^n b^n c^n d^n)
  - Mildly context-sensitive languages

Parsing: O(n^6)

=== 2. DLBA vs NLBA ===

Question: Are deterministic and nondeterministic
          LBAs equivalent?

For TMs: Yes (simulate NTM on DTM)
For LBAs: OPEN PROBLEM!

Most believe: DLBA ≠ NLBA
  - Nondeterminism adds power
  - Some CSLs are not deterministic

But no proof exists.

This is one of the major open problems
in automata theory.

=== Why It's Hard ===

The standard NTM→DTM simulation uses:
  - BFS on computation tree
  - Exponential space

But LBAs have only LINEAR space.
So the simulation doesn't work!

Need a different approach.
No one has found one.

=== Implications ===

If DLBA = NLBA:
  - Deterministic and nondeterministic CSLs same
  - Simplifies theory

If DLBA ≠ NLBA:
  - Nondeterminism adds power
  - More complex theory
  - Some CSLs need nondeterminism

Most believe the latter.
But no proof.
""")

# 3. QUANTUM CSLs
print("""
=== 3. Quantum Context-Sensitive Languages ===

Quantum versions of CSLs:

Quantum LBA:
  - Quantum states
  - Quantum tape
  - Unitary transitions

Power:
  - Probably same as classical LBA (for languages)
  - Different complexity profile

Research area:
  - Quantum automata theory
  - Quantum grammars
  - Quantum complexity

Still experimental.

=== 4. COMPLEXITY CONNECTIONS ===

CSL membership = PSPACE-complete

Related classes:
  - PSPACE: polynomial space
  - NPSPACE = PSPACE (Savitch)
  - EXP: exponential time
  - P ⊆ NP ⊆ PSPACE ⊆ EXP

LBA connections:
  - LBA = linear space
  - NPSPACE = PSPACE
  - So NLBA = DLBA? (Open!)

=== 5. NATURAL LANGUAGE ===

Is natural language context-sensitive?

Evidence FOR:
  - Cross-serial dependencies (Dutch)
  - Some agreement patterns
  - Some word order phenomena

Evidence AGAINST:
  - Most syntax is context-free
  - Mildly context-sensitive might suffice
  - Human parsing is fast (not PSPACE)

Current consensus:
  - Natural language is NOT context-free
  - It's at least mildly context-sensitive
  - Maybe full context-sensitive
  - Still debated

=== 6. BIOINFORMATICS ===

RNA pseudoknots:
  - Crossing base pairs
  - Not context-free
  - Context-sensitive

Protein folding:
  - Complex 3D structure
  - Some aspects context-sensitive
  - Full problem NP-hard

DNA computing:
  - Adleman (1994)
  - Hamiltonian path
  - Context-sensitive operations
""")

# 7. OPEN PROBLEMS
print("""
=== 7. Open Problems ===

1. DLBA vs NLBA
   Are deterministic and nondeterministic
   LBAs equivalent?
   OPEN (believed No)

2. Is natural language context-sensitive?
   Still debated.
   Affects NLP algorithms.

3. CSL parsing complexity
   PSPACE-complete in general.
   But what about subclasses?
   Can we do better for specific CSLs?

4. CSL and circuit complexity
   Connections to NC, P/poly?
   Still being explored.

5. Quantum CSLs
   What is their power?
   Are they useful?
   Early research.

6. CSL and machine learning
   Can we learn CSLs from data?
   Grammar induction for CSLs?
   Hard (undecidable in general).

7. CSL and verification
   Can we verify CSL properties?
   Some are undecidable.
   What about specific properties?

=== 8. RECOMMENDATIONS ===

For students:
  1. Master basic hierarchy first
  2. Understand CSG and LBA
  3. Learn examples (a^n b^n c^n, ww)
  4. Study decidability results
  5. Explore applications

For researchers:
  1. DLBA vs NLBA
  2. Natural language context-sensitivity
  3. CSL parsing algorithms
  4. Quantum CSLs
  5. Applications in bio

For practitioners:
  1. Know when CSLs are needed
  2. Use CFL when possible
  3. Be aware of PSPACE complexity
  4. Consider mildly CS alternatives
  5. Apply to NLP, bio, verification

=== Final Thoughts ===

CSLs are:

✓ COMPLETE THE HIERARCHY
  Between CFL and R.E.

✓ MORE POWERFUL THAN CFL
  Can count multiple things.

✓ MEMBERSHIP DECIDABLE
  PSPACE-complete.

✓ GOOD CLOSURE
  Almost everything.

✓ LESS PRACTICAL
  But important in specialized areas.

✓ OPEN PROBLEMS
  DLBA vs NLBA, natural language.

Key takeaway:
  CSLs are the "middle child" of the hierarchy.
  They fill the gap between CFL and R.E.
  They have interesting properties.
  They appear in natural language and bio.
  And they have open problems.
  
  The Chomsky hierarchy is not just a classification.
  It's a rich theory with deep connections
  and open questions.

"All models are wrong, but some are useful."
  — George Box

CSLs are useful.
They complete the picture.
Go explore them!
""")

# QUICK REFERENCE
print("""
=== Quick Reference ===

Context-Sensitive Grammar:
  Rules: αAβ → αγβ
  Length non-decreasing
  Context matters

Linear Bounded Automaton:
  TM with tape bounded by input
  Linear space O(n)
  Membership: PSPACE-complete

Examples:
  a^n b^n c^n
  ww
  a^i b^j c^k (i < j < k)
  a^n²
  a^n (prime)

Properties:
  - Membership: decidable (PSPACE)
  - Emptiness: undecidable
  - Equivalence: undecidable
  - Closed under union, intersection, complement

Hierarchy:
  Regular ⊊ CFL ⊊ CSL ⊊ R.E.

Open problems:
  - DLBA vs NLBA
  - Natural language context-sensitivity

Key insight:
  CSLs are more powerful than CFL,
  less powerful than TM.
  Membership decidable but expensive.
  Good closure properties.
  Important for theory and applications.
""")