🧠 Introduction

🎯 What is the Chomsky Hierarchy?

The Chomsky Hierarchy is a classification of formal grammars (and the languages they generate) into four levels, from most restrictive (Type 3) to most general (Type 0). Proposed by Noam Chomsky in 1956, it reveals deep connections between grammars, automata, and computational power.

Key insight: Each level corresponds to a different type of machine. As you go up the hierarchy, both the grammars and the machines become more powerful — but also less well-behaved (more undecidable problems).

Why the Hierarchy Matters

Classification: Organizes formal languages. Connections: Grammars ↔ machines. Limits: Power vs decidability. Compilers: Lexer (Type 3), parser (Type 2). Theory: Foundation of CS. Insight: Structure of computation.

🏛️ Four levels📊 Strict inclusion🔄 Grammar ↔ Machine⚖️ Power vs decidability

# Chomsky Hierarchy — the big picture
print("""
=== The Four Levels ===

TYPE 3: REGULAR
  Grammar: A → aB | a (right-linear)
  Machine: Finite automaton (DFA/NFA)
  Example: a*b*, (ab)*
  Memory: None (finite states)

TYPE 2: CONTEXT-FREE
  Grammar: A → α (A is a single nonterminal)
  Machine: Pushdown automaton (PDA)
  Example: a^n b^n, balanced parentheses
  Memory: Stack (LIFO)

TYPE 1: CONTEXT-SENSITIVE
  Grammar: αAβ → αγβ (context matters)
  Machine: Linear bounded automaton (LBA)
  Example: a^n b^n c^n, ww
  Memory: Linear tape (bounded by input)

TYPE 0: RECURSIVELY ENUMERABLE
  Grammar: α → β (no restrictions)
  Machine: Turing machine
  Example: Anything computable
  Memory: Infinite tape

=== The Hierarchy ===

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

  Regular ⊊ Context-Free ⊊ Context-Sensitive ⊊ R.E.

Each inclusion is STRICT!
There are languages at each level
that are not at the lower levels.

=== Why "Chomsky"? ===

Noam Chomsky (born 1928)
  - American linguist
  - Proposed the hierarchy in 1956
  - Revolutionized linguistics
  - Also known for political activism

His insight: natural languages can be
classified by their grammatical structure.
This led to the formal hierarchy.

=== The Grammar-Machine Connection ===

Each grammar type corresponds to a machine:

  Type 3 grammar  ↔  Finite automaton
  Type 2 grammar  ↔  Pushdown automaton
  Type 1 grammar  ↔  Linear bounded automaton
  Type 0 grammar  ↔  Turing machine

This is one of the deepest connections
in computer science!
""")

# ANALOGY
print("=== Analogy: Vehicles on a Road ===")
print("""
Imagine different vehicles:

TYPE 3: BICYCLE
  - Simple, limited
  - Can't carry much
  - Regular languages

TYPE 2: CAR
  - More powerful
  - Can carry more
  - Context-free languages

TYPE 1: TRUCK
  - Even more powerful
  - Can carry heavy loads
  - Context-sensitive languages

TYPE 0: TRAIN
  - Most powerful
  - Can carry anything
  - Recursively enumerable languages

Each can do everything the previous can,
plus more.

But with more power comes more complexity:
  - Harder to control
  - More expensive
  - More undecidable problems

=== Another Analogy: Expressiveness ===

TYPE 3: Can match simple patterns
  "Strings ending in 'ab'"

TYPE 2: Can match nesting
  "Balanced parentheses"

TYPE 1: Can match multiple counts
  "a^n b^n c^n"

TYPE 0: Can compute anything
  "Any algorithm"

Each level adds a new capability.
""")

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

Chomsky Hierarchy:

  Type 3 (Regular)
    ↑ strictly contains
  Type 2 (Context-Free)
    ↑ strictly contains
  Type 1 (Context-Sensitive)
    ↑ strictly contains
  Type 0 (Recursively Enumerable)

Key facts:
  - Each level has a grammar and a machine
  - Each inclusion is strict
  - More power → fewer decidable properties
  - Most practical languages are Type 2 or 3

=== Why It Matters ===

1. COMPILER DESIGN
   - Lexer: Type 3 (regular)
   - Parser: Type 2 (context-free)
   - Semantic analysis: Type 1 or 0

2. LANGUAGE DESIGN
   - Programming languages are Type 2
   - Natural languages are more complex

3. COMPUTABILITY
   - Type 0 = Turing machines
   - Undecidability starts at Type 0

4. COMPLEXITY
   - Each level has different complexity
   - P, NP, PSPACE, etc.

=== The Hierarchy in One Picture ===

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

Each level is strictly contained in the next.
""")

# THE FOUR LEVELS AT A GLANCE
print("=== The Four Levels at a Glance ===")
print(f"{'Type':<8} {'Grammar':<25} {'Machine':<25} {'Memory':<15}")
print("-" * 75)
print(f"{'Type 3':<8} {'A → aB | a':<25} {'Finite automaton':<25} {'None':<15}")
print(f"{'Type 2':<8} {'A → α':<25} {'Pushdown automaton':<25} {'Stack':<15}")
print(f"{'Type 1':<8} {'αAβ → αγβ':<25} {'Linear bounded':<25} {'Linear tape':<15}")
print(f"{'Type 0':<8} {'α → β':<25} {'Turing machine':<25} {'Infinite tape':<15}")

print("""
=== Key Examples ===

Type 3: a*b*, (ab)*, strings ending in "ab"
Type 2: a^n b^n, balanced parens, arithmetic
Type 1: a^n b^n c^n, ww, wcw
Type 0: Anything computable (halting problem, etc.)

=== Decidability ===

Type 3: Everything decidable
Type 2: Membership decidable, but equivalence/ambiguity undecidable
Type 1: Membership decidable (PSPACE), but emptiness undecidable
Type 0: Almost everything undecidable

More power → less decidability!
""")

# WHY IT'S CALLED "CHOMSKY"
print("""
=== History ===

1956: Noam Chomsky publishes
  "Three Models for the Description of Language"

1957: Chomsky's "Syntactic Structures"
  - Revolutionizes linguistics
  - Introduces transformational grammar

1959: Chomsky's "On Certain Formal Properties
  of Grammars"
  - Formalizes the hierarchy

1960s-70s: Hierarchy becomes standard
  - Computer science adopts it
  - Compiler design uses it
  - Automata theory formalizes it

=== Chomsky's Motivation ===

Chomsky was studying NATURAL LANGUAGE:
  - Can we describe English with formal grammars?
  - What grammar type is needed?
  - Are all natural languages the same type?

His conclusion:
  - Natural languages are NOT regular
  - They need at least context-free
  - Possibly more (context-sensitive?)

This led to the hierarchy.

=== Impact ===

The Chomsky hierarchy:
  - Foundation of formal language theory
  - Essential for compiler design
  - Connects linguistics and CS
  - One of the most influential ideas in CS
""")

📊 Overview

🎯 The Four Levels

The Chomsky hierarchy consists of four levels, each defined by progressively less restrictive grammar rules. Each level corresponds to a class of automata and a class of languages.

Hierarchy at a Glance

Type 3: Regular grammars, finite automata. Type 2: Context-free grammars, pushdown automata. Type 1: Context-sensitive grammars, linear bounded automata. Type 0: Unrestricted grammars, Turing machines. Strict: Each inclusion is strict. Trade-off: Power vs decidability.

🔤 Type 3📗 Type 2📘 Type 1🖥️ Type 0

# Overview of the Chomsky Hierarchy
print("=" * 60)
print("OVERVIEW OF THE CHOMSKY HIERARCHY")
print("=" * 60)

print("""
=== The Four Levels ===

TYPE 3: REGULAR GRAMMARS
  Rules: A → aB or A → a
  (Right-linear or left-linear)
  Machine: Finite automaton
  Example: a*b*
  
TYPE 2: CONTEXT-FREE GRAMMARS
  Rules: A → α
  (Single nonterminal on left)
  Machine: Pushdown automaton
  Example: a^n b^n

TYPE 1: CONTEXT-SENSITIVE GRAMMARS
  Rules: αAβ → αγβ
  (Context matters)
  Machine: Linear bounded automaton
  Example: a^n b^n c^n

TYPE 0: UNRESTRICTED GRAMMARS
  Rules: α → β
  (No restrictions)
  Machine: Turing machine
  Example: Anything computable

=== The Hierarchy ===

  Type 3 ⊊ Type 2 ⊊ Type 1 ⊊ Type 0
  
  Regular ⊊ CFL ⊊ CSL ⊊ R.E.

Each inclusion is STRICT:
  - Some CFLs are not regular (a^n b^n)
  - Some CSLs are not CFL (a^n b^n c^n)
  - Some R.E. languages are not CSL (halting problem)

=== Grammar Restrictions ===

Type 3: A → aB | a
  - Single nonterminal on left
  - Right side: terminal + nonterminal, or terminal
  - Very restrictive

Type 2: A → α
  - Single nonterminal on left
  - Right side: any string
  - Context-free

Type 1: αAβ → αγβ
  - Context on left (α, β)
  - Right side: γ (non-empty)
  - Length non-decreasing

Type 0: α → β
  - No restrictions
  - Anything goes

=== Machine Correspondences ===

Type 3 ↔ Finite automaton (DFA/NFA)
Type 2 ↔ Pushdown automaton (PDA)
Type 1 ↔ Linear bounded automaton (LBA)
Type 0 ↔ Turing machine (TM)

Each machine has exactly the power
to recognize its corresponding language class.
""")

# 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-Sensitive':<20} {'Unrestricted':<20}")
print(f"{'Rule form':<25} {'A→aB|a':<20} {'A→α':<20} {'αAβ→αγβ':<20} {'α→β':<20}")
print(f"{'Machine':<25} {'Finite automaton':<20} {'Pushdown':<20} {'Linear bounded':<20} {'Turing machine':<20}")
print(f"{'Memory':<25} {'None':<20} {'Stack':<20} {'Linear tape':<20} {'Infinite tape':<20}")
print(f"{'Example':<25} {'a*b*':<20} {'a^n b^n':<20} {'a^n b^n c^n':<20} {'Any computable':<20}")
print(f"{'Membership':<25} {'O(n)':<20} {'O(n³)':<20} {'PSPACE':<20} {'Undecidable':<20}")
print(f"{'Emptiness':<25} {'Decidable':<20} {'Decidable':<20} {'Undecidable':<20} {'Undecidable':<20}")
print(f"{'Equivalence':<25} {'Decidable':<20} {'Undecidable':<20} {'Undecidable':<20} {'Undecidable':<20}")
print(f"{'Closure ∩':<25} {'Yes':<20} {'No':<20} {'Yes':<20} {'Yes':<20}")
print(f"{'Closure ∪':<25} {'Yes':<20} {'Yes':<20} {'Yes':<20} {'Yes':<20}")
print(f"{'Closure complement':<25} {'Yes':<20} {'No':<20} {'Yes':<20} {'No':<20}")

# VISUAL HIERARCHY
print("""
=== Visual Hierarchy ===

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

Regular ⊊ CFL ⊊ CSL ⊊ R.E.

Each region strictly contains the one inside it.
""")

# WHY STRICT?
print("""
=== Why Are the Inclusions Strict? ===

TYPE 3 ⊊ TYPE 2:
  L = { a^n b^n | n ≥ 0 } is CFL but not regular.
  Proof: Pumping lemma.

TYPE 2 ⊊ TYPE 1:
  L = { a^n b^n c^n | n ≥ 0 } is CSL but not CFL.
  Proof: CFL pumping lemma.

TYPE 1 ⊊ TYPE 0:
  L = { (M, w) | M halts on w } is R.E. but not CSL.
  Proof: Halting problem (undecidable).
  (CSL membership is decidable.)

So each level adds power.

=== The Trade-off ===

As we go UP the hierarchy:
  ↑ More expressive grammars
  ↑ More powerful machines
  ↑ More complex languages
  ↓ Fewer decidable properties
  ↓ Harder to parse
  ↓ Less practical

As we go DOWN:
  ↑ More decidable properties
  ↑ Easier to parse
  ↑ More practical
  ↓ Less expressive

This is the fundamental trade-off
in formal language theory.
""")

# PRACTICAL RELEVANCE
print("""
=== Practical Relevance ===

Where each level appears in practice:

TYPE 3 (REGULAR):
  - Lexical analysis (tokenization)
  - Pattern matching (grep, regex)
  - Protocol parsing (simple)
  - Input validation

TYPE 2 (CONTEXT-FREE):
  - Programming language syntax
  - Expression parsing
  - XML/JSON structure
  - Natural language (approximate)

TYPE 1 (CONTEXT-SENSITIVE):
  - Some natural language phenomena
  - Certain protocol features
  - Type checking (partially)
  - Some bioinformatics patterns

TYPE 0 (RECURSIVELY ENUMERABLE):
  - General computation
  - Anything a computer can do
  - (But usually we use Type 2 or 3!)

=== The Practical Sweet Spot ===

Programming languages are designed as:
  - Lexer: Type 3 (regular)
  - Parser: Type 2 (context-free)
  
Why?
  - Type 3: Fast tokenization
  - Type 2: Efficient parsing (O(n) or O(n³))
  - Type 1+: Too complex, undecidable properties

This is why compilers work!
""")

🔤 Type 3: Regular

🎯 The Simplest Level

Type 3 grammars (regular grammars) are the most restrictive. They generate regular languages, recognized by finite automata. Despite their simplicity, they're widely used in practice.

Type 3 Features

Grammar: A → aB | a. Machine: DFA/NFA. Memory: None (finite states). Example: a*b*, (ab)*. Decidable: Everything. Practical: Lexers, regex.

🔤 Right-linear⚙️ Finite automaton📊 No memory✅ All decidable

# Type 3: Regular Grammars
print("=" * 60)
print("TYPE 3: REGULAR GRAMMARS")
print("=" * 60)

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

A REGULAR GRAMMAR (Type 3) has rules of the form:
  A → aB    (right-linear)
  A → a     (terminal)
  
  or
  
  A → Ba    (left-linear)
  A → a     (terminal)

where:
  A, B are nonterminals
  a is a terminal

=== Right-Linear vs Left-Linear ===

RIGHT-LINEAR:
  A → aB | a
  Nonterminal on the right.
  Generates strings left to right.

LEFT-LINEAR:
  A → Ba | a
  Nonterminal on the left.
  Generates strings right to left.

Both generate the same class (regular languages).
Can convert between them.

=== Examples ===

1. L = a*b*
   S → aS | bB | ε
   B → bB | ε

2. L = (ab)*
   S → aB | ε
   B → bS

3. L = strings ending in "ab"
   S → aS | bS | aB
   B → bC
   C → ε

4. L = strings with even number of 0s
   S → 0A | 1S | ε
   A → 0S | 1A

=== Machine: Finite Automaton ===

Type 3 grammar ↔ Finite automaton (DFA/NFA)

Conversion:
  - Each nonterminal → a state
  - Start symbol → start state
  - A → aB: transition from A to B on 'a'
  - A → a: transition from A to accept state on 'a'

Example:
  Grammar: S → aS | bB | ε
           B → bB | ε
  
  DFA:
    States: {S, B, F}
    Start: S
    Accept: {S, B, F}
    Transitions:
      S --a--> S
      S --b--> B
      B --b--> B
      S --ε--> F (implicit)
      B --ε--> F (implicit)
""")

# REGULAR LANGUAGES IN CODE
print("=== Regular Languages in Code ===")

class DFA:
    """A simple DFA."""
    def __init__(self, states, alphabet, delta, q0, F):
        self.Q = states
        self.Sigma = alphabet
        self.delta = delta
        self.q0 = q0
        self.F = F
    
    def accepts(self, w):
        state = self.q0
        for symbol in w:
            if symbol not in self.Sigma:
                return False
            state = self.delta[(state, symbol)]
        return state in self.F


# Example: DFA for strings ending in "ab"
dfa_ends_ab = DFA(
    states={'q0', 'q1', 'q2'},
    alphabet={'a', 'b'},
    delta={
        ('q0', 'a'): 'q1',
        ('q0', 'b'): 'q0',
        ('q1', 'a'): 'q1',
        ('q1', 'b'): 'q2',
        ('q2', 'a'): 'q1',
        ('q2', 'b'): 'q0',
    },
    q0='q0',
    F={'q2'}
)

print("DFA for strings ending in 'ab':")
for w in ['ab', 'aab', 'bab', 'abab', 'a', 'b', 'ba', '']:
    result = "✓" if dfa_ends_ab.accepts(w) else "✗"
    print(f"  '{w}' → {result}")

# REGULAR GRAMMAR IN CODE
print("""
=== Regular Grammar to DFA ===

Grammar:
  S → aS | bS | aB
  B → bC
  C → ε

DFA:
  States: {S, B, C, F}
  Start: S
  Accept: {C, F}
  
  Transitions:
    S --a--> S
    S --b--> S
    S --a--> B
    B --b--> C
    C --ε--> F

Note: Nondeterministic (S on 'a' can go to S or B).
Convert to DFA via subset construction.
""")

# PROPERTIES
print("""
=== Properties of Regular Languages ===

CLOSURE:
  ✓ Union
  ✓ Intersection
  ✓ Complement
  ✓ Concatenation
  ✓ Kleene star
  ✓ Reversal
  ✓ Homomorphism
  ✓ Inverse homomorphism
  ✓ Difference
  ✓ Symmetric difference

DECISION PROBLEMS:
  ✓ Membership: O(n)
  ✓ Emptiness: decidable
  ✓ Finiteness: decidable
  ✓ Equivalence: decidable
  ✓ Universality: decidable
  ✓ Inclusion: decidable

Everything is decidable!
This is the most well-behaved class.

=== Why So Well-Behaved? ===

Finite automata have:
  - No memory (just finite states)
  - Deterministic (or convert to DFA)
  - Simple structure

This makes all properties decidable.

=== Practical Uses ===

1. LEXICAL ANALYSIS
   - Tokenizing source code
   - Identifiers, numbers, keywords
   - Each token type is regular

2. PATTERN MATCHING
   - grep, regex
   - Search and replace
   - Text processing

3. INPUT VALIDATION
   - Email addresses
   - Phone numbers
   - URLs

4. PROTOCOL PARSING
   - Simple message formats
   - Header parsing

5. HARDWARE
   - Controllers
   - Protocol handlers
   - State machines
""")

# LIMITATIONS
print("""
=== Limitations of Regular Languages ===

Regular languages CANNOT:
  ✗ Count (beyond finite)
  ✗ Match nested structures
  ✗ Remember arbitrary prefixes
  ✗ Handle palindromes
  ✗ Match a^n b^n

WHY?
  Finite automata have finite memory.
  They can't "remember" how many a's they've seen.
  They can't match nested structures.

Examples of NON-regular languages:
  - { a^n b^n | n ≥ 0 }
  - { w | w = w^R } (palindromes)
  - { ww | w ∈ {a,b}* }
  - Balanced parentheses
  - { a^n b^n c^n | n ≥ 0 }

Proof:
  Use the Pumping Lemma for regular languages.

=== The Pumping Lemma ===

If L is regular, there exists p such that
any w ∈ L with |w| ≥ p can be written as
w = xyz where:
  - |xy| ≤ p
  - |y| ≥ 1
  - xy^k z ∈ L for all k ≥ 0

Use to prove non-regularity:
  Assume L is regular.
  Pick w = a^p b^p.
  Show no valid decomposition exists.
  Contradiction. Therefore L is not regular.

=== Why This Matters ===

Regular languages are LIMITED.
For nested structures, we need Type 2 (CFL).
For counting, we need at least Type 2.
For complex patterns, we need Type 1 or 0.
""")

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

Type 3 (Regular):
  Grammar: A → aB | a
  Machine: Finite automaton
  Memory: None

Examples:
  a*b*, (ab)*, strings ending in "ab"

Properties:
  - All decidable
  - Closed under almost everything
  - Very well-behaved

Limitations:
  - Cannot count
  - Cannot nest
  - Cannot match palindromes

Practical uses:
  - Lexical analysis
  - Pattern matching
  - Input validation

Key insight:
  Regular languages are the simplest
  and most practical class.
  But they're limited.
  For more power, go up the hierarchy.
""")

📗 Type 2: Context-Free

🎯 The Programming Language Level

Type 2 grammars (context-free grammars) are more powerful than regular grammars. They can handle nested structures, making them ideal for programming language syntax and parsing.

Type 2 Features

Grammar: A → α (single nonterminal on left). Machine: Pushdown automaton. Memory: Stack (LIFO). Example: a^n b^n, balanced parens. Parsing: O(n³) CYK, O(n) LL/LR. Practical: Programming languages.

📗 A → α🤖 Pushdown📚 Stack memory💻 Programming

# Type 2: Context-Free Grammars
print("=" * 60)
print("TYPE 2: CONTEXT-FREE GRAMMARS")
print("=" * 60)

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

A CONTEXT-FREE GRAMMAR (Type 2) has rules of the form:
  A → α

where:
  A is a single nonterminal
  α is any string of terminals and nonterminals

"Context-free" means:
  A can be replaced by α regardless of context.
  No dependence on surrounding symbols.

=== Examples ===

1. L = a^n b^n
   S → aSb | ε

2. Balanced parentheses
   S → (S) | SS | ε

3. Arithmetic expressions
   E → E + T | T
   T → T * F | F
   F → ( E ) | id

4. Palindromes over {a, b}
   S → aSa | bSb | a | b | ε

5. Programming language syntax
   Program → StmtList
   StmtList → Stmt StmtList | ε
   Stmt → id = Expr ; | if ( Expr ) Stmt | { StmtList }
   Expr → Expr + Term | Term
   Term → Term * Factor | Factor
   Factor → id | ( Expr )

=== Machine: Pushdown Automaton ===

Type 2 grammar ↔ Pushdown automaton (PDA)

PDA = Finite automaton + Stack
  - Can push symbols onto stack
  - Can pop symbols from stack
  - Stack is LIFO (last-in, first-out)

The stack allows:
  - Counting (push for a's, pop for b's)
  - Nesting (push for open, pop for close)
  - Matching (compare symbols)

=== Why "Context-Free"? ===

The rule A → α can be applied:
  - Anywhere A appears
  - Regardless of what's around A
  
This is what "context-free" means.

Contrast with Type 1:
  αAβ → αγβ
  A can only be replaced in specific contexts.

=== Derivation ===

A derivation is a sequence of rule applications:
  S ⇒ α₁ ⇒ α₂ ⇒ ... ⇒ w

Example: S → aSb | ε
  S ⇒ aSb ⇒ aaSbb ⇒ aabb
  So aabb ∈ L(G).

=== Parse Trees ===

A parse tree shows the structure:
  - Root: start symbol
  - Internal: nonterminals
  - Leaves: terminals
  - Each node: a rule application

Example for "aabb":
      S
     /|\
    a S b
     /|\
    a S b
      |
      ε
""")

# CONTEXT-FREE LANGUAGES IN CODE
print("=== Context-Free Languages in Code ===")

class CFG:
    """A simple context-free grammar."""
    def __init__(self, start, rules):
        self.start = start
        self.rules = rules  # dict: nonterminal -> list of productions
    
    def generate(self, symbol=None, max_depth=10):
        """Generate a random string."""
        import random
        if symbol is None:
            symbol = self.start
        
        if max_depth <= 0:
            if symbol not in self.rules:
                return symbol
            # Pick shortest production
            prods = sorted(self.rules[symbol], key=lambda p: len(p))
            return self.generate(prods[0], 0)
        
        if symbol not in self.rules:
            return symbol
        
        prod = random.choice(self.rules[symbol])
        return ''.join(self.generate(s, max_depth - 1) for s in prod)
    
    def accepts(self, string, max_len=20):
        """Check if string can be derived (brute force)."""
        from collections import deque
        
        queue = deque([(self.start, 0)])
        visited = set()
        
        for _ in range(100000):
            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) + 5:
                continue
            
            # Expand leftmost nonterminal
            for i, c in enumerate(current):
                if c in self.rules:
                    for prod in self.rules[c]:
                        new = current[:i] + prod + current[i+1:]
                        if len(new) <= len(string) + 5:
                            queue.append((new, depth + 1))
                    break
        
        return False


# Example: a^n b^n
anbn = CFG('S', {'S': ['aSb', '']})

print("CFG for a^n b^n: S → aSb | ε")
print("\nGenerated strings:")
for _ in range(8):
    s = anbn.generate(max_depth=5)
    print(f"  '{s}'")

print("\nAcceptance test:")
for s in ['', 'ab', 'aabb', 'aaabbb', 'aab', 'abb', 'ba']:
    result = "✓" if anbn.accepts(s) else "✗"
    print(f"  '{s}' → {result}")

# Example: balanced parentheses
paren = CFG('S', {'S': ['(S)', 'SS', '()']})

print("\nCFG for balanced parentheses: S → (S) | SS | ()")
print("\nAcceptance test:")
for s in ['()', '(())', '()()', '((()))', '(()', ')(']:
    result = "✓" if paren.accepts(s) else "✗"
    print(f"  '{s}' → {result}")

# PROPERTIES
print("""
=== Properties of Context-Free Languages ===

CLOSURE:
  ✓ Union
  ✗ Intersection (of two CFLs)
  ✗ Complement
  ✓ Concatenation
  ✓ Kleene star
  ✓ Reversal
  ✓ Homomorphism
  ✓ Inverse homomorphism
  ✓ Intersection with regular

DECISION PROBLEMS:
  ✓ Membership: O(n³) CYK, O(n) LL/LR
  ✓ Emptiness: decidable
  ✓ Finiteness: decidable
  ✗ Equivalence: undecidable
  ✗ Ambiguity: undecidable
  ✗ Universality: undecidable
  ✗ Inclusion: undecidable

Mixed decidability:
  Some problems decidable, some not.
  More than regular, less than context-sensitive.

=== Why Some Problems Are Undecidable ===

Equivalence:
  If we could decide L(G1) = L(G2) for CFGs,
  we could decide ambiguity.
  But ambiguity is undecidable.
  So equivalence is undecidable.

Ambiguity:
  No algorithm can decide if a CFG is ambiguous.
  This is a fundamental limitation.

Universality:
  Given CFG G, is L(G) = Σ*?
  Undecidable (related to equivalence).
""")

# NORMAL FORMS
print("""
=== Normal Forms ===

CFGs can be converted to normal forms:

CHOMSKY NORMAL FORM (CNF):
  A → BC | a
  (Binary or terminal rules)
  Used by CYK algorithm.

GREIBACH NORMAL FORM (GNF):
  A → aα
  (Starts with terminal)
  Used for top-down parsing.

Conversion:
  Any CFG can be converted to CNF or GNF.
  Preserves the language.

=== Parsing Algorithms ===

CYK (Cocke-Younger-Kasami):
  - O(n³) time
  - Requires CNF
  - Dynamic programming

Earley:
  - O(n³) general
  - O(n²) for unambiguous
  - O(n) for LL/LR
  - Any CFG

LL(k):
  - O(n) time
  - Top-down
  - Predictive parsing
  - Requires LL(k) grammar

LR(k):
  - O(n) time
  - Bottom-up
  - Shift-reduce parsing
  - Most powerful deterministic

=== Practical Uses ===

1. PROGRAMMING LANGUAGES
   - Syntax specification
   - Parser generation
   - Expression parsing

2. COMPILERS
   - Lexer (Type 3)
   - Parser (Type 2)
   - AST construction

3. DATA FORMATS
   - JSON, XML, YAML
   - Configuration files
   - Markup languages

4. NATURAL LANGUAGE
   - Sentence structure
   - Phrase structure grammars
   - (Approximation)

5. BIOINFORMATICS
   - RNA secondary structure
   - Sequence patterns
""")

# LIMITATIONS
print("""
=== Limitations of Context-Free Languages ===

CFLs CANNOT:
  ✗ Count two independent things
  ✗ Match a^n b^n c^n
  ✗ Handle ww (copying)
  ✗ Enforce cross-serial dependencies
  ✗ Some natural language phenomena

WHY?
  One stack = one counter.
  Can't count two things independently.
  Can't copy arbitrary strings.

Examples of NON-CFLs:
  - { a^n b^n c^n | n ≥ 0 }
  - { ww | w ∈ {a,b}* }
  - { a^i b^j c^k | i < j < k }
  - { a^n | n is prime }

Proof:
  Use the CFL pumping lemma.

=== The CFL Pumping Lemma ===

If L is a CFL, there exists p such that
any w ∈ L with |w| ≥ p can be written as
w = uvxyz where:
  - |vxy| ≤ p
  - |vy| ≥ 1
  - uv^k xy^k z ∈ L for all k ≥ 0

Use to prove non-context-freeness.

=== Why This Matters ===

CFLs are the sweet spot for programming languages:
  - Powerful enough for syntax
  - Efficient to parse
  - Decidable enough for compilers

But some things need more power:
  - Semantic analysis (Type 1 or 0)
  - Natural language (Type 1?)
  - Complex protocols (Type 1)
""")

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

Type 2 (Context-Free):
  Grammar: A → α
  Machine: Pushdown automaton
  Memory: Stack

Examples:
  a^n b^n, balanced parens, arithmetic expressions

Properties:
  - Membership decidable (O(n³) or O(n))
  - Equivalence undecidable
  - Ambiguity undecidable
  - Closed under union, concat, star
  - NOT closed under intersection, complement

Practical uses:
  - Programming language syntax
  - Parsing
  - Data formats
  - Natural language (approximation)

Key insight:
  Context-free grammars are the sweet spot
  for programming languages.
  Powerful enough for syntax.
  Efficient enough for compilers.
""")

📘 Type 1: Context-Sensitive

🎯 The Context Matters Level

Type 1 grammars (context-sensitive grammars) allow rules where a nonterminal can only be replaced in a specific context. They're more powerful than CFGs but less powerful than unrestricted grammars.

Type 1 Features

Grammar: αAβ → αγβ (context-sensitive). Machine: Linear bounded automaton. Memory: Linear tape (bounded). Example: a^n b^n c^n, ww. Membership: Decidable (PSPACE). Practical: Natural language, some protocols.

📘 αAβ → αγβ🤖 LBA📏 Linear tape🔬 Research

# Type 1: Context-Sensitive Grammars
print("=" * 60)
print("TYPE 1: CONTEXT-SENSITIVE GRAMMARS")
print("=" * 60)

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

A CONTEXT-SENSITIVE GRAMMAR (Type 1) has rules:
  αAβ → αγβ

where:
  A is a nonterminal
  α, β are strings (context)
  γ is a non-empty string

Key features:
  - Context on both sides (α, β)
  - Replacement depends on context
  - Length non-decreasing (|αγβ| ≥ |αAβ|)
  - No ε-productions (except S → ε)

=== 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!

=== Examples ===

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

   This generates a^n b^n c^n.
   The context-sensitive rules (CB → BC)
   reorder symbols to match counts.

2. L = ww (w ∈ {a,b}*)
   Context-sensitive grammar exists.

3. L = { a^i b^j c^k | i < j < k }
   Context-sensitive.

4. Natural language phenomena
   Cross-serial dependencies in Dutch.

=== Machine: Linear Bounded Automaton ===

Type 1 grammar ↔ Linear bounded automaton (LBA)

LBA = Turing machine with bounded tape
  - Tape length = input length (or linear)
  - Can't use more space than input
  - Can read/write/move on bounded tape

Properties:
  - More powerful than PDA (has full tape access)
  - Less powerful than TM (bounded tape)
  - Membership decidable (PSPACE)
  - Emptiness undecidable

=== Why Linear Bounded? ===

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

This means the string never shrinks.
So the tape never needs to grow beyond input.
Hence, linear bounded automaton.

=== Length Non-Decreasing ===

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

So strings never shrink.
This is the key property.

Exception: S → ε (only for start symbol).
""")

# CONTEXT-SENSITIVE LANGUAGES IN CODE
print("=== Context-Sensitive Languages in Code ===")

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 accepts(self, string, max_steps=1000):
        """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)
print("Context-sensitive grammar for a^n b^n c^n:")
print("""
  S → aSBC | aBC
  CB → BC
  aB → ab
  bB → bb
  bC → bc
  cC → cc
""")

# Simpler example: a^n b^n c^n with small n
# This grammar is complex; let's just demonstrate the concept
csg_example = CSG('S', [
    ('S', 'aBC'),
    ('S', 'aSBC'),
    ('CB', 'BC'),
    ('aB', 'ab'),
    ('bB', 'bb'),
    ('bC', 'bc'),
    ('cC', 'cc'),
])

print("Testing (limited):")
for s in ['abc', 'aabbcc']:
    result = csg_example.accepts(s, max_steps=5000)
    print(f"  '{s}' → {'✓' if result else '✗ (may need more steps)'}")

# PROPERTIES
print("""
=== Properties of Context-Sensitive Languages ===

CLOSURE:
  ✓ Union
  ✓ Intersection
  ✓ Complement
  ✓ Concatenation
  ✓ Kleene star
  ✓ Reversal
  ✓ Homomorphism
  ✓ Inverse homomorphism

DECISION PROBLEMS:
  ✓ Membership: decidable (PSPACE)
  ✗ Emptiness: undecidable
  ✗ Equivalence: undecidable
  ✗ Universality: undecidable
  ✗ Inclusion: undecidable
  ✗ Finiteness: undecidable

Mixed:
  Membership is decidable.
  Most other problems are not.

=== Membership: PSPACE ===

Given CSG G and string w:
  - |w| = n
  - LBA uses O(n) space
  - Simulate LBA on w
  - Time: exponential (but space: polynomial)
  - PSPACE-complete in general

So membership is decidable,
but may be expensive.

=== Why Emptiness is Undecidable ===

Given CSG G, is L(G) = ∅?
  - Related to halting problem
  - LBA can simulate TMs
  - Undecidable

=== Practical Relevance ===

Context-sensitive languages appear in:
  - Some natural language phenomena
  - Certain protocol specifications
  - Type checking (partially)
  - Some bioinformatics patterns

But they're not as practical as Type 2 or 3:
  - Parsing is expensive (PSPACE)
  - Most problems undecidable
  - Hard to design grammars

=== The Gap ===

Type 1 is less studied than Type 2 or 3:
  - Too complex for practical parsing
  - Too weak for general computation
  - "Middle child" of the hierarchy

But it's theoretically important:
  - Completes the hierarchy
  - Connects CFL and R.E.
  - Has interesting properties
""")

# NATURAL LANGUAGE
print("""
=== Context-Sensitive and Natural Language ===

Chomsky's motivation:
  - Are natural languages context-free?
  - Or do they need more power?

Evidence for context-sensitivity:
  - Cross-serial dependencies (Dutch)
  - Some agreement phenomena
  - Certain nested structures

Example (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 can.

Debate:
  - Some linguists: natural language is context-sensitive
  - Others: context-free with extra features
  - Still an open question

=== Why This Matters ===

If natural language is context-sensitive:
  - Parsing is harder (PSPACE)
  - But still decidable

If context-free:
  - Efficient parsing (O(n³) or O(n))
  - Simpler models

The answer affects:
  - Computational linguistics
  - NLP algorithms
  - Cognitive science
""")

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

Type 1 (Context-Sensitive):
  Grammar: αAβ → αγβ
  Machine: Linear bounded automaton
  Memory: Linear tape (bounded by input)

Examples:
  a^n b^n c^n, ww, cross-serial dependencies

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

Practical uses:
  - Some natural language phenomena
  - Certain protocol specifications
  - Type checking (partially)

Key insight:
  Context-sensitive grammars are the "middle child"
  of the Chomsky hierarchy.
  More powerful than CFG, less than TM.
  Membership is decidable but expensive.
  Most other problems are undecidable.
""")

🖥️ Type 0: Recursively Enumerable

🎯 The Most Powerful Level

Type 0 grammars (unrestricted grammars) have no restrictions on their rules. They generate exactly the recursively enumerable languages, recognized by Turing machines. This is the most powerful level of the Chomsky hierarchy.

Type 0 Features

Grammar: α → β (no restrictions). Machine: Turing machine. Memory: Infinite tape. Example: Anything computable. Membership: Undecidable. Practical: General computation.

🖥️ α → β🤖 Turing machine♾️ Infinite tape❌ Undecidable

# Type 0: Unrestricted Grammars
print("=" * 60)
print("TYPE 0: UNRESTRICTED GRAMMARS")
print("=" * 60)

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

An UNRESTRICTED GRAMMAR (Type 0) has rules of the form:
  α → β

where:
  α is a non-empty string of symbols
  β is any string of symbols

No restrictions!
  - α can be any string (not just a nonterminal)
  - β can be any string (including ε)
  - Length can decrease

=== Why "Unrestricted"? ===

Compare:
  Type 3: A → aB | a (very restricted)
  Type 2: A → α (single nonterminal on left)
  Type 1: αAβ → αγβ (context, length non-decreasing)
  Type 0: α → β (no restrictions)

Type 0 is the most general.
It can express any computation.

=== Examples ===

1. Anything computable
   - Any algorithm
   - Any program
   - Any Turing machine

2. Halting problem
   - HALT = { (M, w) | M halts on w }
   - Recursively enumerable, not decidable

3. Diophantine equations
   - Hilbert's 10th problem
   - Recursively enumerable

4. Post Correspondence Problem
   - PCP
   - Recursively enumerable

5. Any language recognized by a TM

=== Machine: Turing Machine ===

Type 0 grammar ↔ Turing machine (TM)

TM = Finite automaton + Infinite tape
  - Can read/write any cell
  - Can move left or right
  - Unlimited memory

The TM is the most powerful model:
  - Can compute anything computable
  - Defines the limits of computation

=== Equivalence ===

Type 0 grammars = Turing machines
  - Same power
  - Can convert between them

Grammar → TM:
  - Use TM to search for derivations
  - Undecidable in general (derivation search may not halt)

TM → Grammar:
  - Encode TM configurations as strings
  - Grammar rules simulate TM transitions
  - Accepting computation corresponds to derivation

Both directions possible.
Therefore equivalent.
""")

# RECURSIVELY ENUMERABLE LANGUAGES
print("""
=== Recursively Enumerable Languages ===

A language L is RECURSIVELY ENUMERABLE (r.e.) if:
  There's a TM M that accepts L.
  
  M(w) = accept if w ∈ L
  M(w) = loop or reject if w ∉ L

Key property:
  - "Yes" instances are recognizable
  - "No" instances may not be

Examples:
  - HALT (halting problem)
  - Any decidable language
  - Any language recognized by a program

=== Recognizable vs Decidable ===

RECOGNIZABLE (r.e.):
  - TM accepts if w ∈ L
  - May loop if w ∉ L

DECIDABLE (recursive):
  - TM always halts
  - Accepts if w ∈ L, rejects if w ∉ L

Relationship:
  Decidable ⊊ Recognizable

Example:
  HALT is recognizable but not decidable.
  HALT^c is not recognizable.

=== The Hierarchy ===

  All Languages
  ┌─────────────────────────────┐
  │                             │
  │   Recognizable (r.e.)       │
  │   ┌─────────────────────┐   │
  │   │                     │   │
  │   │   Decidable         │   │
  │   │   (Recursive)       │   │
  │   │                     │   │
  │   └─────────────────────┘   │
  │                             │
  └─────────────────────────────┘

Type 0 = Recognizable
Decidable ⊊ Type 0
""")

# PROPERTIES
print("""
=== Properties of Recursively Enumerable Languages ===

CLOSURE:
  ✓ Union
  ✓ Intersection
  ✗ Complement (NOT closed!)
  ✓ Concatenation
  ✓ Kleene star
  ✓ Reversal
  ✓ Homomorphism
  ✓ Inverse homomorphism

DECISION PROBLEMS:
  ✗ Membership: undecidable
  ✗ Emptiness: undecidable
  ✗ Equivalence: undecidable
  ✗ Universality: undecidable
  ✗ Almost everything: undecidable

Only a few things are decidable:
  - Whether a string is in a specific r.e. language
    (may not halt if not in)
  - Whether the language is non-empty
    (may not halt)

=== Why So Undecidable? ===

Turing machines can:
  - Simulate any computation
  - Self-reference (diagonalization)
  - Lead to paradoxes

This causes:
  - Halting problem undecidable
  - Rice's theorem: all semantic properties undecidable
  - Almost everything undecidable

=== The Halting Problem ===

HALT = { (M, w) | M halts on w }
  - Recognizable (simulate M on w)
  - Not decidable (diagonalization)
  - Not co-recognizable

This is the fundamental undecidable problem.
All other undecidability reduces to it.
""")

# PRACTICAL RELEVANCE
print("""
=== Practical Relevance ===

Type 0 = general computation:
  - Any program
  - Any algorithm
  - Any computer

But in practice:
  - We don't use Type 0 grammars directly
  - We use programming languages
  - But they're all Type 0 (Turing-complete)

Why?
  - Type 0 is too powerful
  - Parsing is undecidable
  - Can't verify properties

So we use:
  - Type 3 for lexing
  - Type 2 for parsing
  - Type 0 for computation

=== The Full Pipeline ===

Source code → Lexer (Type 3) → Tokens
           → Parser (Type 2) → AST
           → Semantic Analysis (Type 1?) → IR
           → Optimization (Type 0) → Code
           → Code Generation (Type 0) → Machine code

Each phase uses the appropriate level!

=== Why Not Use Type 0 Everywhere? ===

Because:
  - Parsing Type 0 is undecidable
  - Can't check properties
  - Can't optimize reliably
  - Can't verify correctness

So we structure languages:
  - Simple syntax (Type 2)
  - Complex semantics (Type 0)
  - This gives us the best of both worlds
""")

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

Type 0 (Unrestricted):
  Grammar: α → β
  Machine: Turing machine
  Memory: Infinite tape

Examples:
  Any computable language
  HALT, PCP, Hilbert's 10th

Properties:
  - Membership undecidable
  - Almost everything undecidable
  - Closed under union, intersection
  - NOT closed under complement

Practical uses:
  - General computation
  - Programming languages (semantics)
  - Anything a computer can do

Key insight:
  Type 0 is the most powerful level.
  It defines the limits of computation.
  But it's too powerful for practical parsing.
  We use lower levels for structure,
  and Type 0 for computation.
""")

🔗 Relationships

🎯 How the Levels Connect

The four levels of the Chomsky hierarchy form a strict inclusion chain. Each level has a corresponding grammar type, machine type, and language class. Understanding these relationships is key to the theory.

Key Relationships

Inclusion: Type 3 ⊊ Type 2 ⊊ Type 1 ⊊ Type 0. Grammar ↔ Machine: Each grammar type matches a machine. Closure: More power = different closure. Decidability: Less power = more decidable. Examples: Separating languages. Trade-off: Power vs tractability.

📊 Strict inclusion🔄 Grammar ↔ Machine⚖️ Power vs decidability🎯 Separating examples

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

print("""
=== The Inclusion Chain ===

Type 3 ⊊ Type 2 ⊊ Type 1 ⊊ Type 0

Regular ⊊ Context-Free ⊊ Context-Sensitive ⊊ R.E.

Each inclusion is STRICT:
  - There are languages at each level
    that are not at the lower levels.
  - Proved by separating examples.

=== The Grammar-Machine Correspondence ===

Type 3 grammar ↔ Finite automaton
Type 2 grammar ↔ Pushdown automaton
Type 1 grammar ↔ Linear bounded automaton
Type 0 grammar ↔ Turing machine

This is a bijection:
  - Every grammar has a machine
  - Every machine has a grammar
  - They recognize the same languages

=== The Language Classes ===

Type 3: Regular languages
  - Simplest
  - All decidable
  - No memory

Type 2: Context-free languages
  - Nested structures
  - Some undecidable properties
  - Stack memory

Type 1: Context-sensitive languages
  - Context matters
  - Membership decidable
  - Linear tape

Type 0: Recursively enumerable languages
  - Most general
  - Almost everything undecidable
  - Infinite tape

=== The Trade-off ===

As we go UP the hierarchy:
  ↑ More expressive grammars
  ↑ More powerful machines
  ↑ More complex languages
  ↓ Fewer decidable properties
  ↓ Harder to parse
  ↓ Less practical

As we go DOWN:
  ↑ More decidable properties
  ↑ Easier to parse
  ↑ More practical
  ↓ Less expressive

This is the fundamental trade-off.
""")

# SEPARATING EXAMPLES
print("""
=== Separating Examples ===

To show Type 3 ⊊ Type 2:
  L = { a^n b^n | n ≥ 0 }
  - Context-free: S → aSb | ε
  - Not regular: pumping lemma
  
To show Type 2 ⊊ Type 1:
  L = { a^n b^n c^n | n ≥ 0 }
  - Context-sensitive: CSG exists
  - Not context-free: CFL pumping lemma

To show Type 1 ⊊ Type 0:
  L = { (M, w) | M halts on w }
  - Recursively enumerable: simulate M on w
  - Not context-sensitive: CSL membership decidable,
    but HALT membership undecidable

Each example separates two levels.
Together, they prove all inclusions are strict.

=== More Separating Examples ===

Type 3 vs Type 2:
  - a^n b^n
  - Palindromes
  - Balanced parentheses

Type 2 vs Type 1:
  - a^n b^n c^n
  - ww
  - a^i b^j c^k (i < j < k)

Type 1 vs Type 0:
  - HALT
  - Any undecidable r.e. language
  - PCP

=== The Pattern ===

Each level can do something
the lower level can't:
  Type 3: Simple patterns
  Type 2: Nesting
  Type 1: Multiple counts
  Type 0: Anything computable
""")

# CLOSURE PROPERTIES COMPARISON
print("""
=== Closure Properties Comparison ===

              Regular  CFL    CSL    R.E.
Union         ✓        ✓      ✓      ✓
Intersection  ✓        ✗      ✓      ✓
Complement    ✓        ✗      ✓      ✗
Concat        ✓        ✓      ✓      ✓
Star          ✓        ✓      ✓      ✓
Reversal      ✓        ✓      ✓      ✓
Homomorphism  ✓        ✓      ✓      ✓

Key observations:
  - Regular: closed under almost everything
  - CFL: NOT closed under intersection, complement
  - CSL: closed under intersection, complement
  - R.E.: NOT closed under complement

This is surprising:
  - CFL loses some closure properties
  - CSL regains them
  - R.E. loses complement

=== Why? ===

Regular:
  - Finite states
  - Can do product constructions
  - Complement easy (swap accept)

CFL:
  - Stack is LIFO
  - Can't easily intersect two CFLs
  - Complement requires determinism

CSL:
  - Linear tape
  - Can simulate intersection
  - Complement via determinism

R.E.:
  - Infinite tape
  - Can't complement
  - (If it could, HALT would be decidable!)
""")

# DECISION PROBLEMS COMPARISON
print("""
=== Decision Problems Comparison ===

              Regular  CFL    CSL    R.E.
Membership    ✓ O(n)   ✓ O(n³) ✓ PSPACE ✗
Emptiness     ✓        ✓      ✗      ✗
Finiteness    ✓        ✓      ✗      ✗
Equivalence   ✓        ✗      ✗      ✗
Universality  ✓        ✗      ✗      ✗
Ambiguity     N/A      ✗      ✗      ✗

Key observations:
  - Regular: everything decidable
  - CFL: membership/emptiness/finiteness decidable
  - CSL: only membership decidable
  - R.E.: almost nothing decidable

=== The Decidability Landscape ===

As we go UP the hierarchy:
  More power → less decidability

This is the fundamental trade-off.

=== Why Membership is Always Decidable? ===

For Regular:
  - Simulate DFA
  - O(n) time

For CFL:
  - CYK algorithm
  - O(n³) time

For CSL:
  - Simulate LBA
  - PSPACE

For R.E.:
  - Simulate TM
  - May not halt!
  - Undecidable
""")

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

Inclusion:
  Type 3 ⊊ Type 2 ⊊ Type 1 ⊊ Type 0

Grammar-Machine:
  Type 3 ↔ Finite automaton
  Type 2 ↔ Pushdown automaton
  Type 1 ↔ Linear bounded automaton
  Type 0 ↔ Turing machine

Separating Examples:
  Type 3 vs 2: a^n b^n
  Type 2 vs 1: a^n b^n c^n
  Type 1 vs 0: HALT

Closure:
  Regular: most closed
  CFL: less closed
  CSL: more closed
  R.E.: least closed

Decidability:
  Regular: all decidable
  CFL: some decidable
  CSL: only membership
  R.E.: almost none

Key insight:
  The Chomsky hierarchy reveals
  the deep structure of computation.
  Power and decidability trade off.
  Understanding this structure is
  fundamental to computer science.
""")

📐 Separation Proofs

🎯 Proving the Inclusions Are Strict

To prove the Chomsky hierarchy is strict, we need to show that each level contains languages not in the level below. This is done using separating examples and pumping lemmas.

Proof Techniques

Pumping lemma: For regular and CFL. Diagonalization: For Type 1 vs Type 0. Closure properties: Indirect proofs. Separating examples: One language per gap. Contradiction: Assume lower level, derive contradiction. Structure: Each proof separates two levels.

💧 Pumping📐 Diagonal🔒 Closure🎯 Example

# Separation Proofs
print("=" * 60)
print("SEPARATION PROOFS")
print("=" * 60)

print("""
=== What We Need to Prove ===

To show the hierarchy is strict:

1. Type 3 ⊊ Type 2:
   Find a CFL that is not regular.

2. Type 2 ⊊ Type 1:
   Find a CSL that is not context-free.

3. Type 1 ⊊ Type 0:
   Find an r.e. language that is not context-sensitive.

Each proof uses different techniques.
""")

# PROOF 1: TYPE 3 VS TYPE 2
print("""
=== Proof 1: Regular ⊊ Context-Free ===

Claim: L = { a^n b^n | n ≥ 0 } is CFL but NOT regular.

Part A: L is context-free.
  Grammar: S → aSb | ε
  This generates a^n b^n.
  So L is context-free. ✓

Part B: L is NOT regular.
  Proof by pumping lemma:
  
  Assume L is regular with pumping length p.
  Choose w = a^p b^p ∈ L.
  By pumping lemma: w = xyz with:
    |xy| ≤ p
    |y| ≥ 1
    xy^k z ∈ L for all k ≥ 0
  
  Since |xy| ≤ p, y consists only of a's.
  So y = a^m for some m ≥ 1.
  
  Take k = 0: xy^0 z = xz = a^(p-m) b^p.
  This has p-m a's and p b's.
  Since m ≥ 1, p-m ≠ p.
  So xz ∉ L. Contradiction!
  
  Therefore, L is not regular. ∎
  
Conclusion: Regular ⊊ Context-Free. ✓
""")

# PROOF 2: TYPE 2 VS TYPE 1
print("""
=== Proof 2: Context-Free ⊊ Context-Sensitive ===

Claim: L = { a^n b^n c^n | n ≥ 0 } is CSL but NOT CFL.

Part A: L is context-sensitive.
  Grammar: S → aSBC | aBC
           CB → BC
           aB → ab
           bB → bb
           bC → bc
           cC → cc
  
  This generates a^n b^n c^n.
  So L is context-sensitive. ✓

Part B: L is NOT context-free.
  Proof by CFL pumping lemma:
  
  Assume L is CFL with pumping length p.
  Choose w = a^p b^p c^p ∈ L.
  By pumping lemma: w = uvxyz with:
    |vxy| ≤ p
    |vy| ≥ 1
    uv^k xy^k z ∈ L for all k ≥ 0
  
  Since |vxy| ≤ p, vxy spans at most 2 of the 3 blocks
  (a-block, b-block, c-block).
  
  Case 1: vxy in a-block only.
    Pumping changes a count only.
    uv²xy²z has more a's than b's or c's.
    ∉ L. Contradiction.
    
  Case 2: vxy in b-block only.
    Similar. ∉ L.
    
  Case 3: vxy in c-block only.
    Similar. ∉ L.
    
  Case 4: vxy spans a-block and b-block.
    Pumping changes a and b counts but not c.
    uv²xy²z has c count unchanged, a/b changed.
    For equality: a=b=c needed. But c is fixed.
    ∉ L. Contradiction.
    
  Case 5: vxy spans b-block and c-block.
    Similar. ∉ L.
  
  In all cases, contradiction.
  Therefore, L is not context-free. ∎
  
Conclusion: Context-Free ⊊ Context-Sensitive. ✓
""")

# PROOF 3: TYPE 1 VS TYPE 0
print("""
=== Proof 3: Context-Sensitive ⊊ Recursively Enumerable ===

Claim: L = { (M, w) | M halts on w } is r.e. but NOT CSL.

Part A: L is recursively enumerable.
  Recognizer:
    Given (M, w):
      1. Simulate M on w
      2. If M halts, accept
      3. If M loops, loop
  
  This recognizes L.
  So L is r.e. ✓

Part B: L is NOT context-sensitive.
  Proof:
    If L were context-sensitive,
    then membership in L would be decidable
    (since CSL membership is decidable).
    
    But membership in HALT is undecidable
    (halting problem).
    
    Contradiction!
    
  Therefore, L is not context-sensitive. ∎
  
Conclusion: Context-Sensitive ⊊ Recursively Enumerable. ✓

=== Key Point ===

CSL membership is decidable.
HALT membership is undecidable.
So HALT is not CSL.
But HALT is r.e.
So CSL ⊊ R.E.
""")

# CLOSURE-BASED PROOFS
print("""
=== Closure-Based Proofs ===

Sometimes it's easier to use closure properties.

Example: Prove { ww | w ∈ {a,b}* } is not CFL.

Proof:
  Assume L = { ww } is CFL.
  
  Let R = a*b*a*b* (regular).
  Then L ∩ R = { a^i b^j a^i b^j } (CFL ∩ regular = CFL).
  
  But { a^i b^j a^i b^j } is not CFL.
  (Can prove by CFL pumping lemma.)
  
  Contradiction!
  Therefore, L is not CFL. ∎

=== Another Example ===

Prove { a^i b^j c^k | i < j < k } is not CFL.

Proof:
  Assume L is CFL.
  
  Let L1 = { a^i b^j c^k | i < j, k arbitrary } (CFL)
  Let L2 = { a^i b^j c^k | j < k, i arbitrary } (CFL)
  
  L1 ∩ L2 = { a^i b^j c^k | i < j < k } = L
  
  If CFLs were closed under intersection,
  L would be CFL. But it's not.
  
  (This shows CFLs are not closed under intersection.)
  
  Actually, this doesn't directly prove L is not CFL.
  Need a different approach.
  
  Better: Use CFL pumping lemma directly.
""")

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

Separation proofs:

1. REGULAR ⊊ CFL
   Example: a^n b^n
   Technique: Regular pumping lemma

2. CFL ⊊ CSL
   Example: a^n b^n c^n
   Technique: CFL pumping lemma

3. CSL ⊊ R.E.
   Example: HALT
   Technique: Decidability of CSL membership

Each proof uses a different technique.
Together, they prove all inclusions are strict.

=== Key Techniques ===

- PUMPING LEMMA
  For regular and context-free languages.

- DIAGONALIZATION
  For undecidability (Type 1 vs Type 0).

- CLOSURE PROPERTIES
  Indirect proofs using intersections, complements.

- SEPARATING EXAMPLES
  One language per gap in the hierarchy.

=== Why This Matters ===

The strictness of the hierarchy shows:
  - Each level adds genuine power
  - No level is redundant
  - The hierarchy is meaningful

This is why we have four levels,
not three or five.
Each captures something distinct.
""")

📝 Grammar Comparison

🎯 Four Types of Grammars

Each level of the Chomsky hierarchy has a corresponding grammar type, distinguished by the form of their production rules. The restrictions on rules determine the power of the grammar.

Grammar Rules

Type 3: A → aB | a (right-linear). Type 2: A → α (single nonterminal). Type 1: αAβ → αγβ (context). Type 0: α → β (unrestricted). Restriction: Less restrictive = more powerful. Length: Type 1 non-decreasing.

🔤 A → aB📗 A → α📘 αAβ → αγβ🖥️ α → β

# Grammar Comparison
print("=" * 60)
print("GRAMMAR COMPARISON")
print("=" * 60)

print("""
=== The Four Grammar Types ===

TYPE 3: REGULAR GRAMMAR
  Rules: A → aB | a
  (Right-linear: nonterminal at right end)
  or
  A → Ba | a
  (Left-linear: nonterminal at left end)
  
  Restrictions:
    - Single nonterminal on left
    - Right side: terminal + nonterminal, or terminal
    - Very restrictive

TYPE 2: CONTEXT-FREE GRAMMAR
  Rules: A → α
  where α ∈ (V ∪ Σ)*
  
  Restrictions:
    - Single nonterminal on left
    - Right side: any string
    - Context-free

TYPE 1: CONTEXT-SENSITIVE GRAMMAR
  Rules: αAβ → αγβ
  where γ ≠ ε
  
  Restrictions:
    - Context on left (α, β)
    - Right side: non-empty γ
    - Length non-decreasing

TYPE 0: UNRESTRICTED GRAMMAR
  Rules: α → β
  where α ≠ ε
  
  Restrictions:
    - None!
    - α can be any string
    - β can be any string (including ε)
    - Length can decrease

=== Visual Comparison ===

Type 3:  A → aB | a
         (Very restricted)

Type 2:  A → α
         (Context-free)

Type 1:  αAβ → αγβ
         (Context-sensitive)

Type 0:  α → β
         (Unrestricted)

=== Examples ===

Type 3: a*b*
  S → aS | bB | ε
  B → bB | ε

Type 2: a^n b^n
  S → aSb | ε

Type 1: a^n b^n c^n
  S → aSBC | aBC
  CB → BC
  aB → ab
  ...

Type 0: Any computable language
  (No simple example, but very general)
""")

# GRAMMAR GENERATION POWER
print("""
=== Generation Power ===

Each grammar type can generate:

Type 3:
  - Regular languages
  - a*b*, (ab)*, strings ending in "ab"
  - All finite languages

Type 2:
  - Context-free languages
  - a^n b^n, balanced parens
  - Programming language syntax
  - Natural language (approximate)

Type 1:
  - Context-sensitive languages
  - a^n b^n c^n, ww
  - Some natural language phenomena
  - Cross-serial dependencies

Type 0:
  - Recursively enumerable languages
  - Anything computable
  - HALT, PCP, Hilbert's 10th
  - Any program's language

=== The Generation Process ===

Start with start symbol S.
Apply rules to replace symbols.
Continue until string of terminals.

Derivation: S ⇒ α₁ ⇒ α₂ ⇒ ... ⇒ w

Type 3: Right-linear derivation
  - Replace rightmost nonterminal
  - Builds string left to right

Type 2: Context-free derivation
  - Replace any nonterminal
  - Builds parse tree

Type 1: Context-sensitive derivation
  - Replace in context
  - More complex

Type 0: Unrestricted derivation
  - Any replacement
  - Most general
""")

# GRAMMAR NORMAL FORMS
print("""
=== Normal Forms ===

Each grammar type has normal forms:

TYPE 3:
  Right-linear or left-linear
  (No specific "normal form" beyond this)

TYPE 2:
  Chomsky Normal Form (CNF): A → BC | a
  Greibach Normal Form (GNF): A → aα
  Both preserve the language.

TYPE 1:
  No standard normal form.
  But can restrict to length-preserving or
  length-increasing rules.

TYPE 0:
  No standard normal form.
  Can restrict to rules of certain forms
  (e.g., α → β with |α| ≤ 2).

=== Why Normal Forms? ===

Normal forms:
  - Simplify proofs
  - Enable algorithms (CYK needs CNF)
  - Reveal structure
  - Standardize representation

Every grammar can be converted to
an equivalent one in normal form.
""")

# CONVERSION BETWEEN TYPES
print("""
=== Conversion Between Types ===

Can we convert between types?

Type 3 → Type 2:
  ✓ Every regular grammar is a CFG.
  (Just relax the restrictions.)

Type 2 → Type 1:
  ✓ Every CFG is a CSG.
  (Context-free is a special case of context-sensitive.)

Type 1 → Type 0:
  ✓ Every CSG is an unrestricted grammar.
  (Just relax the restrictions.)

Type 2 → Type 3:
  ✗ Not always. a^n b^n is CFL but not regular.

Type 1 → Type 2:
  ✗ Not always. a^n b^n c^n is CSL but not CFL.

Type 0 → Type 1:
  ✗ Not always. HALT is r.e. but not CSL.

=== The Pattern ===

Going UP: Always possible.
Going DOWN: Not always possible.

This is the essence of the hierarchy:
  Each level is strictly more powerful.
""")

# SUMMARY TABLE
print("=== Summary Table ===")
print(f"{'Type':<8} {'Grammar Rule':<20} {'Restriction':<25} {'Power':<15}")
print("-" * 70)
print(f"{'Type 3':<8} {'A → aB | a':<20} {'Right-linear':<25} {'Regular':<15}")
print(f"{'Type 2':<8} {'A → α':<20} {'Single nonterminal':<25} {'Context-Free':<15}")
print(f"{'Type 1':<8} {'αAβ → αγβ':<20} {'Context, non-decreasing':<25} {'Context-Sens.':<15}")
print(f"{'Type 0':<8} {'α → β':<20} {'None':<25} {'R.E.':<15}")

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

1. RESTRICTION INCREASES DECIDABILITY
   More restrictive grammar → more decidable properties.

2. RESTRICTION DECREASES POWER
   More restrictive grammar → fewer languages.

3. CONTEXT IS KEY
   Type 2 vs Type 1: context-free vs context-sensitive.

4. LEFT SIDE MATTERS
   Type 3: A on left
   Type 2: A on left
   Type 1: αAβ on left (context)
   Type 0: α on left (any)

5. LENGTH MATTERS
   Type 1: non-decreasing (|αγβ| ≥ |αAβ|)
   Type 0: can decrease

These restrictions define the hierarchy.
""")

🤖 Machine Comparison

🎯 Four Types of Machines

Each grammar type corresponds to a machine type. The machines differ in their memory: none, stack, linear tape, or infinite tape. This memory determines their computational power.

Machine Types

Type 3: Finite automaton (no memory). Type 2: Pushdown automaton (stack). Type 1: Linear bounded automaton (linear tape). Type 0: Turing machine (infinite tape). Memory: Determines power. Correspondence: Grammar ↔ Machine.

⚙️ Finite📚 Stack📏 Linear♾️ Infinite

# Machine Comparison
print("=" * 60)
print("MACHINE COMPARISON")
print("=" * 60)

print("""
=== The Four Machine Types ===

TYPE 3: FINITE AUTOMATON (DFA/NFA)
  Components:
    - Finite set of states
    - Input tape (read-only, left-to-right)
    - Transition function
  
  Memory: NONE (only current state)
  
  Power: Regular languages
  Example: a*b*
  Complexity: O(n) membership

TYPE 2: PUSHDOWN AUTOMATON (PDA)
  Components:
    - Finite set of states
    - Input tape (read-only)
    - STACK (unbounded, LIFO)
    - Transition function
  
  Memory: STACK (last-in, first-out)
  
  Power: Context-free languages
  Example: a^n b^n
  Complexity: O(n³) membership (CYK)

TYPE 1: LINEAR BOUNDED AUTOMATON (LBA)
  Components:
    - Finite set of states
    - Tape (read/write, bounded by input length)
    - Head (read/write/move)
  
  Memory: LINEAR TAPE (bounded by input)
  
  Power: Context-sensitive languages
  Example: a^n b^n c^n
  Complexity: PSPACE membership

TYPE 0: TURING MACHINE (TM)
  Components:
    - Finite set of states
    - Tape (read/write, INFINITE)
    - Head (read/write/move)
  
  Memory: INFINITE TAPE
  
  Power: Recursively enumerable languages
  Example: HALT
  Complexity: Undecidable membership

=== The Memory Hierarchy ===

  No memory → Stack → Linear tape → Infinite tape
  (Type 3)   (Type 2)  (Type 1)     (Type 0)
  
  Increasing memory → increasing power

=== Visual Comparison ===

Type 3: Finite Automaton
  ┌─────┐
  │ FSM │──→ Read input
  └─────┘

Type 2: Pushdown Automaton
  ┌─────┐
  │ FSM │──→ Read input
  └──┬──┘
     │
  ┌──┴──┐
  │Stack│
  └─────┘

Type 1: Linear Bounded Automaton
  ┌─────┐
  │ FSM │──→ Read/Write tape
  └──┬──┘    (bounded by input)
     │
  ┌──┴──────────────┐
  │ Linear tape     │
  └─────────────────┘

Type 0: Turing Machine
  ┌─────┐
  │ FSM │──→ Read/Write tape
  └──┬──┘    (infinite)
     │
  ┌──┴──────────────┐
  │ Infinite tape   │
  └─────────────────┘
""")

# MEMORY AND POWER
print("""
=== Memory and Power ===

The key difference between machines is MEMORY:

Type 3: No memory
  - Can only remember current state
  - Finite states → finite memory
  - Can't count or nest

Type 2: Stack (LIFO)
  - Can push/pop symbols
  - One stack → one counter
  - Can nest and match

Type 1: Linear tape (bounded)
  - Can read/write anywhere on tape
  - Tape length = input length
  - Can do more complex operations

Type 0: Infinite tape
  - Can read/write anywhere
  - Unlimited memory
  - Can compute anything

=== The Memory Hierarchy ===

No memory ⊊ Stack ⊊ Linear tape ⊊ Infinite tape

Each type of memory gives more power:
  - No memory: regular
  - Stack: context-free
  - Linear: context-sensitive
  - Infinite: r.e.

=== Why Memory Determines Power ===

With no memory:
  - Can't count beyond finite
  - Can't match nested structures

With stack:
  - Can count (push/pop)
  - Can match nesting
  - But only one counter

With linear tape:
  - Can access any position
  - Can count multiple things
  - But bounded by input

With infinite tape:
  - Can do anything
  - Unlimited computation
  - Full power
""")

# COMPLEXITY COMPARISON
print("""
=== Complexity Comparison ===

Membership:
  Type 3: O(n) — simulate DFA
  Type 2: O(n³) — CYK algorithm
  Type 1: PSPACE — simulate LBA
  Type 0: Undecidable — simulate TM may not halt

Space:
  Type 3: O(1) — just current state
  Type 2: O(n) — stack can grow to n
  Type 1: O(n) — tape bounded by input
  Type 0: Unbounded — may use any space

Time:
  Type 3: Linear
  Type 2: Cubic (general), linear (LL/LR)
  Type 1: Exponential (but polynomial space)
  Type 0: Unbounded (may not halt)

=== The Complexity Trade-off ===

More power → more complexity
  - Type 3: Easy
  - Type 2: Moderate
  - Type 1: Hard
  - Type 0: Impossible (in general)

This is why we use lower types in practice.
""")

# SUMMARY TABLE
print("=== Summary Table ===")
print(f"{'Type':<8} {'Machine':<25} {'Memory':<15} {'Complexity':<15}")
print("-" * 65)
print(f"{'Type 3':<8} {'Finite automaton':<25} {'None':<15} {'O(n)':<15}")
print(f"{'Type 2':<8} {'Pushdown automaton':<25} {'Stack':<15} {'O(n³)':<15}")
print(f"{'Type 1':<8} {'Linear bounded':<25} {'Linear tape':<15} {'PSPACE':<15}")
print(f"{'Type 0':<8} {'Turing machine':<25} {'Infinite tape':<15} {'Undecidable':<15}")

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

1. MEMORY DETERMINES POWER
   More memory → more power.

2. STACK IS KEY FOR NESTING
   Type 2 uses stack for nesting.
   This is why CFGs are used for syntax.

3. LINEAR TAPE FOR MULTIPLE COUNTS
   Type 1 uses tape for multiple counters.
   This handles a^n b^n c^n.

4. INFINITE TAPE FOR EVERYTHING
   Type 0 uses infinite tape for general computation.
   This handles anything computable.

5. COMPLEXITY TRADES OFF
   More power → more complexity.
   This is why practical languages use Type 2 or 3.

=== Practical Machine Choices ===

Lexer: DFA (Type 3)
Parser: PDA (Type 2)
Semantic analysis: LBA (Type 1) or TM (Type 0)
General computation: TM (Type 0)

Each phase uses the appropriate machine.
""")

💼 Applications

🎯 Chomsky Hierarchy in Practice

The Chomsky hierarchy isn't just theory — it guides the design of compilers, programming languages, and data formats. Understanding which level a problem belongs to helps choose the right tools and techniques.

Application Areas

Compilers: Lexer (Type 3), parser (Type 2). Languages: Syntax (Type 2), semantics (Type 0). Data formats: JSON/XML (Type 2). Natural language: Type 1 or 2. Protocols: Type 2 or 3. Bioinformatics: Type 2 or 1.

💻 Compilers📝 Languages📄 Data🧬 Bio

# Applications of the Chomsky Hierarchy
print("=" * 60)
print("APPLICATIONS OF THE CHOMSKY HIERARCHY")
print("=" * 60)

# 1. COMPILER DESIGN
print("""
=== 1. Compiler Design ===

Compilers use all levels of the hierarchy:

LEXICAL ANALYSIS (Type 3):
  - Tokenize source code
  - Each token type: regular language
  - Identifiers, numbers, keywords, operators
  - Tool: Lex, Flex

SYNTAX ANALYSIS (Type 2):
  - Parse token stream
  - Grammar: context-free
  - Build parse tree / AST
  - Tool: Yacc, Bison, ANTLR

SEMANTIC ANALYSIS (Type 1/0):
  - Type checking
  - Scope resolution
  - Some properties undecidable

CODE GENERATION (Type 0):
  - Any computation
  - Optimization (undecidable in general)
  - Register allocation (NP-hard)

The pipeline:
  Source → Lexer → Tokens → Parser → AST
         → Semantic → IR → Optimizer → Code

Each phase uses the appropriate level.
""")

# 2. PROGRAMMING LANGUAGES
print("""
=== 2. Programming Languages ===

Programming language syntax is Type 2 (CFG):
  - Expressions
  - Statements
  - Declarations
  - Blocks

Examples:
  C, Java, Python, JavaScript syntax
  All described by context-free grammars.

Why Type 2?
  - Powerful enough for nesting
  - Efficient parsing (O(n) or O(n³))
  - Well-understood theory
  - Good tools available

Semantic analysis needs more:
  - Type checking (Type 1?)
  - Data flow analysis (Type 0)
  - Program verification (undecidable)

=== Language Design ===

Designers aim for:
  - Unambiguous Type 2 grammar
  - Deterministic parsing (LL/LR)
  - Good error messages

This is why languages have:
  - Keywords (avoid ambiguity)
  - Braces (explicit nesting)
  - Semicolons (statement terminators)
  - Operator precedence (defined by grammar)
""")

# 3. DATA FORMATS
print("""
=== 3. Data Formats ===

Many data formats are Type 2:

JSON:
  value → object | array | string | number | true | false | null
  object → { members } | { }
  members → pair | pair , members
  pair → string : value
  array → [ elements ] | [ ]
  elements → value | value , elements

XML:
  element →  content 
  content → element | text | content content

YAML:
  (indentation-based, but still CFG-like)

These require nesting, so Type 2 is needed.
Regex (Type 3) can't parse them correctly.

=== 4. NATURAL LANGUAGE ===

Natural language is more complex:
  - Some phenomena are context-free
  - Some are context-sensitive
  - Some may be more

Examples of context-sensitive:
  - Cross-serial dependencies (Dutch)
  - Agreement patterns
  - Some word order phenomena

Debate: Is natural language Type 1 or Type 2?
  - Most linguists: Type 2 or weakly Type 1
  - Some: Type 1
  - None: Type 0 (too powerful)

This affects NLP algorithms.
""")

# 5. PROTOCOLS
print("""
=== 5. Network Protocols ===

Many protocols are Type 2 or Type 3:

HTTP:
  request → method SP url SP version CRLF headers CRLF body
  headers → header | header CRLF headers
  header → name : value
  (Context-free)

SMTP:
  command → HELO | MAIL | RCPT | DATA | QUIT | ...
  (Regular or context-free)

SIP:
  message → request | response
  (Context-free)

Protocols with nested structures need Type 2.
Simple protocols can use Type 3.

=== 6. BIOINFORMATICS ===

Biological sequences have structure:

RNA secondary structure:
  S → a S u | c S g | g S c | u S a | S S | ε
  (Context-free)

This models:
  - Stems (base pairs)
  - Loops
  - Branches

DNA patterns:
  - Some are regular
  - Some are context-free
  - Some are context-sensitive

Used in:
  - RNA folding prediction
  - Sequence analysis
  - Drug design
""")

# 7. SUMMARY TABLE
print("=== Application Summary ===")
print(f"{'Domain':<25} {'Level':<15} {'Example':<30}")
print("-" * 70)
print(f"{'Lexical analysis':<25} {'Type 3':<15} {'Tokenization':<30}")
print(f"{'Syntax analysis':<25} {'Type 2':<15} {'Parsing':<30}")
print(f"{'Semantic analysis':<25} {'Type 1/0':<15} {'Type checking':<30}")
print(f"{'Code generation':<25} {'Type 0':<15} {'Optimization':<30}")
print(f"{'Data formats':<25} {'Type 2':<15} {'JSON, XML':<30}")
print(f"{'Natural language':<25} {'Type 1/2':<15} {'Sentence structure':<30}")
print(f"{'Protocols':<25} {'Type 2/3':<15} {'HTTP, SMTP':<30}")
print(f"{'Bioinformatics':<25} {'Type 2/1':<15} {'RNA folding':<30}")

# 8. THE PRACTICAL SWEET SPOT
print("""
=== The Practical Sweet Spot ===

Most practical applications use:
  - Type 3: For simple patterns and tokenization
  - Type 2: For structured syntax and parsing

Why?
  - Type 3: Fast, simple, all decidable
  - Type 2: Good balance of power and tractability
  - Type 1: Too complex for most practical parsing
  - Type 0: Too powerful, undecidable

The hierarchy guides:
  - What's possible (expressiveness)
  - What's practical (complexity)
  - What tools to use (automata, parsers)

=== Design Principles ===

1. USE THE LOWEST SUFFICIENT LEVEL
   Don't use Type 2 if Type 3 works.
   Simpler is better.

2. SEPARATE CONCERNS
   Lexer (Type 3) → Parser (Type 2) → Semantics (Type 0)
   Each phase uses the right level.

3. DESIGN FOR PARSABILITY
   Unambiguous Type 2 grammars
   Deterministic parsing (LL/LR)
   Good error messages

4. KNOW THE LIMITS
   Type 2 can't do everything.
   Type 1 and 0 are needed for some things.
   But they're harder to use.
""")

# 9. CASE STUDY: PYTHON
print("""
=== Case Study: Python ===

Python's design reflects the Chomsky hierarchy:

LEXER (Type 3):
  - Tokenizes source code
  - Uses regular expressions
  - Identifies keywords, identifiers, numbers, etc.

PARSER (Type 2):
  - Uses a PEG parser (since 3.9)
  - Context-free grammar
  - Builds AST
  - O(n) parsing for most inputs

SEMANTIC ANALYSIS (Type 1/0):
  - Type checking (dynamic in Python)
  - Scope resolution
  - Some properties undecidable

COMPILATION (Type 0):
  - Compiles to bytecode
  - Optimization (limited by undecidability)
  - Runtime execution

=== The Pipeline ===

  Source → Lexer → Tokens → Parser → AST
         → Compiler → Bytecode → Interpreter

Each phase uses the appropriate level.
Python's design is a practical application
of the Chomsky hierarchy.
""")

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

1. KNOW YOUR LEVEL
   - What level is your problem?
   - Type 3: Regular expressions
   - Type 2: Parsers
   - Type 1: Complex patterns
   - Type 0: General computation

2. USE THE RIGHT TOOLS
   - Type 3: grep, regex, DFA
   - Type 2: Yacc, ANTLR, CYK
   - Type 1: Custom algorithms
   - Type 0: Any programming language

3. DESIGN LANGUAGES WISELY
   - Syntax: Type 2 (context-free)
   - Semantics: Type 1 or 0
   - Keep syntax simple and parseable

4. UNDERSTAND LIMITS
   - Type 3: Can't nest
   - Type 2: Can't count twice
   - Type 1: Hard to parse
   - Type 0: Undecidable

5. APPLY THE HIERARCHY
   - Compilers use all levels
   - Languages use Type 2
   - Data formats use Type 2
   - Protocols use Type 2 or 3

Key insight:
  The Chomsky hierarchy is not just theory.
  It's a practical guide for
  language design, compiler construction,
  and problem solving in computer science.
""")

🚀 Beyond Chomsky

🎯 Extensions and Alternatives

The Chomsky hierarchy is the classic classification, but there are many extensions, refinements, and alternative hierarchies. These address limitations of the original and explore new dimensions of computation.

Beyond the Basics

Mildly context-sensitive: Between Type 2 and Type 1. Tree automata: Trees instead of strings. Probabilistic: PCFGs, weighted automata. Quantum: Quantum grammars. Bio-inspired: DNA, membrane. Hierarchies: Time, space, circuit.

🌳 Tree📊 Probabilistic⚛️ Quantum🧬 Bio

# Beyond the Chomsky Hierarchy
print("=" * 60)
print("BEYOND THE CHOMSKY HIERARCHY")
print("=" * 60)

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

Between Type 2 (CFL) and Type 1 (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)

All are weakly equivalent (generate same 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

=== 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. TREE AUTOMATA
print("""
=== 2. Tree Automata ===

Instead of strings, process TREES:

Types:
  - Bottom-up tree automata
  - Top-down tree automata
  - Tree walking automata

Applications:
  - XML validation
  - Compiler ASTs
  - Term rewriting
  - Program analysis

Hierarchy:
  Regular tree languages
  Context-free tree languages
  ...

Analogy to Chomsky:
  String automata ↔ Tree automata
  Regular strings ↔ Regular trees
  Context-free strings ↔ Context-free trees

=== 3. PROBABILISTIC GRAMMARS ===

Add probabilities to rules:

PCFG:
  A → α with probability p

Used in:
  - NLP parsing
  - Speech recognition
  - Machine translation

Algorithms:
  - Inside-outside
  - Viterbi
  - CYK (probabilistic)

=== 4. WEIGHTED AUTOMATA ===

Each transition has a weight:

Weighted finite automata (WFA):
  - Transitions have weights
  - Accept with a weight
  - Compute weighted languages

Used in:
  - Speech recognition
  - Machine learning
  - NLP
""")

# 5. QUANTUM GRAMMARS
print("""
=== 5. Quantum Grammars ===

Quantum versions of formal grammars:

Quantum CFG:
  - Rules have quantum amplitudes
  - Superposition of derivations
  - Measurement at end

Quantum automata:
  - Quantum finite automata (QFA)
  - Quantum pushdown automata
  - Quantum Turing machines

Research area:
  - Quantum natural language processing
  - Quantum compiler design
  - Theoretical computer science

Still experimental.

=== 6. BIO-INSPIRED COMPUTING ===

Models inspired by biology:

DNA Computing:
  - Uses DNA molecules
  - Adleman (1994): Hamiltonian path
  - Massively parallel
  - TM-equivalent (probably)

Membrane Computing:
  - P systems
  - Compartments with rules
  - Different variants
  - Some are TM-equivalent

Neural Computing:
  - Artificial neural networks
  - Spiking neural networks
  - TM-equivalent (with enough neurons)

All are computational models,
but different from the Chomsky hierarchy.
""")

# 7. COMPLEXITY HIERARCHIES
print("""
=== 7. Complexity Hierarchies ===

Beyond Chomsky, there are complexity hierarchies:

TIME:
  P ⊆ NP ⊆ PSPACE ⊆ EXP ⊆ ...

SPACE:
  L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE ⊆ ...

CIRCUIT:
  NC ⊆ AC ⊆ TC ⊆ P/poly

POLYNOMIAL HIERARCHY:
  P ⊆ NP ⊆ Σ₂ ⊆ Σ₃ ⊆ ... ⊆ PSPACE

These refine our understanding of computation.

=== 8. PARAMETERIZED COMPLEXITY ===

Complexity with parameters:

FPT: Fixed-Parameter Tractable
  - Time: O(f(k) · n^c)
  - Tractable for small k

W[1]-hard:
  - Believed not FPT

Examples:
  - Vertex Cover: FPT (O(2^k · n))
  - Clique: W[1]-hard

This is a different dimension of complexity.

=== 9. FINE-GRAINED COMPLEXITY ===

Exact complexity of specific problems:

3SUM: O(n²) best known
APSP: O(n³) best known
SETH: SAT requires ~2^n time

Conditional lower bounds:
  If 3SUM is hard, then ... is hard.

This refines P vs NP.
""")

# 10. OPEN QUESTIONS
print("""
=== 10. Open Questions ===

1. IS NATURAL LANGUAGE CONTEXT-FREE?
   - Some evidence for context-sensitive
   - Debate continues
   - Affects NLP algorithms

2. ARE THERE USEFUL LEVELS BETWEEN TYPE 2 AND TYPE 1?
   - Mildly context-sensitive
   - Multiple context-free grammars
   - Still being explored

3. CAN WE UNIFY DIFFERENT HIERARCHIES?
   - Chomsky hierarchy
   - Complexity hierarchies
   - Parameterized complexity
   - Is there a grand unified theory?

4. WHAT IS THE RIGHT MODEL FOR NATURAL LANGUAGE?
   - Context-free?
   - Mildly context-sensitive?
   - Something else?

5. QUANTUM GRAMMARS
   - What is their power?
   - Are they useful?
   - Still early research

6. BIO-INSPIRED MODELS
   - DNA computing
   - Membrane computing
   - What is their power?

These are active research areas.
""")

# 11. RECOMMENDATIONS
print("""
=== Recommendations ===

For students:
  1. Master the basic hierarchy
  2. Understand grammar-machine correspondence
  3. Learn pumping lemmas
  4. Study applications (compilers, NLP)
  5. Explore extensions

For researchers:
  1. Mildly context-sensitive languages
  2. Quantum grammars
  3. Tree automata
  4. Probabilistic grammars
  5. Complexity hierarchies

For practitioners:
  1. Know which level your problem is
  2. Use appropriate tools
  3. Design for parseability
  4. Understand complexity trade-offs
  5. Apply the hierarchy

=== Final Thoughts ===

The Chomsky hierarchy is:

✓ FOUNDATIONAL
  Classification of formal languages.

✓ CONNECTED
  Grammars ↔ Machines ↔ Languages.

✓ PRACTICAL
  Guides compiler design, language design.

✓ EXTENSIBLE
  Tree automata, probabilistic, quantum.

✓ EVOLVING
  New models, new hierarchies.

✓ BEAUTIFUL
  Deep structure of computation.

Key takeaway:
  The Chomsky hierarchy is not just a classification.
  It's a way of understanding computation itself.
  It reveals the trade-offs between
  power, decidability, and complexity.
  
  Master the hierarchy, and you understand
  the landscape of formal languages.

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

The Chomsky hierarchy is useful.
It's the foundation of formal language theory.
Go explore it!
""")

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

Type 3: Regular
  Grammar: A → aB | a
  Machine: Finite automaton
  Memory: None
  Example: a*b*
  Membership: O(n)

Type 2: Context-Free
  Grammar: A → α
  Machine: Pushdown automaton
  Memory: Stack
  Example: a^n b^n
  Membership: O(n³)

Type 1: Context-Sensitive
  Grammar: αAβ → αγβ
  Machine: Linear bounded automaton
  Memory: Linear tape
  Example: a^n b^n c^n
  Membership: PSPACE

Type 0: Recursively Enumerable
  Grammar: α → β
  Machine: Turing machine
  Memory: Infinite tape
  Example: HALT
  Membership: Undecidable

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

Key insight:
  More power → less decidability.
  More power → more complexity.
  Choose the right level for your problem.
""")