# WORKSHEET G2 — Collision Breaking with Parse-Tree Features
## Verifiable with any calculator and pencil. No English inside formulas.

---

## PART A: The Collision (count characters by hand)

**Byte classes (8 buckets):**
| Class | Bytes |
|-------|-------|
| 0 | control (0-31) |
| 1 | punct-low (!-/ = 33-47) |
| 2 | digits (0-9 = 48-57) |
| 3 | punct-mid (:-@ = 58-64) |
| 4 | upper (A-Z = 65-90) |
| 5 | punct-high ([-` = 91-96) |
| 6 | lower (a-z = 97-122) |
| 7 | extended (123-255) |

---

**STRING 1:** "a+b=c" (5 characters)

| Char | ASCII | Class |
|------|-------|-------|
| a | 97 | 6 |
| + | 43 | 1 |
| b | 98 | 6 |
| = | 61 | 3 |
| c | 99 | 6 |

**Counts:** class 0=0, class 1=1, class 2=0, class 3=1, class 4=0, class 5=0, class 6=3, class 7=0

**Probability vector F("a+b=c"):**
```
(0, 1/5, 0, 1/5, 0, 0, 3/5, 0) = (0, 0.2, 0, 0.2, 0, 0, 0.6, 0)
```

---

**STRING 2:** "x+y=z" (5 characters)

| Char | ASCII | Class |
|------|-------|-------|
| x | 120 | 6 |
| + | 43 | 1 |
| y | 121 | 6 |
| = | 61 | 3 |
| z | 122 | 6 |

**Counts:** class 0=0, class 1=1, class 2=0, class 3=1, class 4=0, class 5=0, class 6=3, class 7=0

**Probability vector F("x+y=z"):**
```
(0, 1/5, 0, 1/5, 0, 0, 3/5, 0) = (0, 0.2, 0, 0.2, 0, 0, 0.6, 0)
```

---

**STRING 3:** "p/q=r" (5 characters)

| Char | ASCII | Class |
|------|-------|-------|
| p | 112 | 6 |
| / | 47 | 1 |
| q | 113 | 6 |
| = | 61 | 3 |
| r | 114 | 6 |

**Counts:** class 0=0, class 1=1, class 2=0, class 3=1, class 4=0, class 5=0, class 6=3, class 7=0

**Probability vector F("p/q=r"):**
```
(0, 1/5, 0, 1/5, 0, 0, 3/5, 0) = (0, 0.2, 0, 0.2, 0, 0, 0.6, 0)
```

---

**VERIFICATION:** All three vectors are identical.
```
F("a+b=c") = F("x+y=z") = F("p/q=r") = (0, 0.2, 0, 0.2, 0, 0, 0.6, 0)
```

**COLLISION CONFIRMED:** Three different equations → one probability vector.

Type the counts into calculator. Verify they match.

---

## PART B: Parse-Tree Features (count by hand)

**Node types for arithmetic expressions:**
| Type | Code |
|------|------|
| variable | V |
| binary_op_add | B+ |
| binary_op_div | B/ |
| binary_op_eq | B= |

---

**STRING 1:** "a+b=c"

Parse tree: (a + b) = c
Nodes: V(a), B+(+), V(b), B+(=) → wait, "=" is binary_op_eq

Correct parse tree:
```
      B= 
     /  \
   B+    V(c)
  /  \
V(a) V(b)
```

**Node count:** V=3, B+=1, B==1, B/=0

**Total nodes:** 5

**Probability vector τ("a+b=c"):**
```
(V, B+, B=, B/) = (3/5, 1/5, 1/5, 0) = (0.6, 0.2, 0.2, 0)
```

---

**STRING 2:** "x+y=z"

Parse tree:
```
      B=
     /  \
   B+    V(z)
  /  \
V(x) V(y)
```

**Node count:** V=3, B+=1, B==1, B/=0

**Probability vector τ("x+y=z"):**
```
(V, B+, B=, B/) = (3/5, 1/5, 1/5, 0) = (0.6, 0.2, 0.2, 0)
```

---

**STRING 3:** "p/q=r"

Parse tree:
```
      B=
     /  \
   B/    V(r)
  /  \
V(p) V(q)
```

**Node count:** V=3, B+=0, B==1, B/=1

**Probability vector τ("p/q=r"):**
```
(V, B+, B=, B/) = (3/5, 0, 1/5, 1/5) = (0.6, 0, 0.2, 0.2)
```

---

**VERIFICATION:**
```
τ("a+b=c") = (0.6, 0.2, 0.2, 0)
τ("x+y=z") = (0.6, 0.2, 0.2, 0)
τ("p/q=r") = (0.6, 0, 0.2, 0.2)
```

τ("a+b=c") = τ("x+y=z") ✗ (still collides!)
τ("a+b=c") ≠ τ("p/q=r") ✓ (broken!)

"a+b=c" and "x+y=z" have the same structure (addition, then equality).
"p/q=r" has different structure (division, then equality).

To break ALL collisions, we need a 3rd feature that distinguishes "a+b=c" from "x+y=z". These differ only in variable names, which is semantically irrelevant.

**CONCLUSION:** τ breaks operator-type collisions (addition vs division) but NOT variable-name collisions (a+b=c vs x+y=z). This is CORRECT: the two equations are semantically equivalent (both are addition-then-equality).

---

## PART C: Product Fisher Distance (computed numerically)

**FORMULA:** d²_F((p,r), (q,s)) = d²_F(p,q) + d²_F(r,s)

**INPUT 1:** p = F("a+b=c") = (0, 0.2, 0, 0.2, 0, 0, 0.6, 0)
**INPUT 2:** q = F("p/q=r") = (0, 0.2, 0, 0.2, 0, 0, 0.6, 0)
**NOTE:** F is identical for these two strings.

**INPUT 3:** r = τ("a+b=c") = (0.6, 0.2, 0.2, 0)
**INPUT 4:** s = τ("p/q=r") = (0.6, 0, 0.2, 0.2)

**STEP 1: Compute d_F(p,q)**
```
p = q = (0, 0.2, 0, 0.2, 0, 0, 0.6, 0)
√(pᵢqᵢ) = pᵢ  (since p = q)
Sum = 0 + 0.2 + 0 + 0.2 + 0 + 0 + 0.6 + 0 = 1.0
d_F(p,q) = 2·arccos(1.0) = 2·0 = 0
```

**STEP 2: Compute d_F(r,s)**
```
r = (0.6, 0.2, 0.2, 0)
s = (0.6, 0, 0.2, 0.2)

√(r₁s₁) = √(0.6 × 0.6) = 0.6
√(r₂s₂) = √(0.2 × 0) = 0
√(r₃s₃) = √(0.2 × 0.2) = 0.2
√(r₄s₄) = √(0 × 0.2) = 0

Sum = 0.6 + 0 + 0.2 + 0 = 0.8
```

**WORK on calculator:**
```
2 * arccos(0.8)
```

**RESULT:** d_F(r,s) = 2 × 0.6435 = 1.2870

**STEP 3: Product distance**
```
d²_F((p,r), (q,s)) = 0² + (1.2870)² = 1.6564
d_F((p,r), (q,s)) = √1.6564 = 1.2870
```

**VERIFY on calculator:**
```
sqrt(0 + (2*arccos(0.8))^2)
```

**OUTPUT:** 1.2870

**INTERPRETATION:** F alone gives distance 0 (collision). τ alone gives distance 1.2870 (distinguishes). Product gives 1.2870 (τ provides all the discrimination).

---

## PART D: Marginal Projection (computed numerically)

**FORMULA:** π(p,r) = p

**CLAIM:** d_F(π(x), π(y)) ≤ d_F(x,y)

**TEST:** x = (p,r), y = (q,s) from Part C.

**LEFT SIDE:** d_F(π(x), π(y)) = d_F(p,q) = 0
**RIGHT SIDE:** d_F(x,y) = 1.2870

**CHECK:** 0 ≤ 1.2870 ✓

The projection does not increase distance.

---

## PART E: Another Example — "1+2" vs "3+4"

**STRING 4:** "1+2" (3 characters)

| Char | ASCII | Class |
|------|-------|-------|
| 1 | 49 | 2 |
| + | 43 | 1 |
| 2 | 50 | 2 |

**F("1+2") = (0, 1/3, 2/3, 0, 0, 0, 0, 0) = (0, 0.333, 0.667, 0, 0, 0, 0, 0)**

Parse tree:
```
  B+
 /  \
N(1) N(2)
```
Node types: N=2, B+=1, B==0, B/=0, V=0

**τ("1+2") = (0, 1/3, 0, 0, 2/3) = (0, 0.333, 0, 0, 0.667)** 

(using 5 types: V, B+, B=, B/, N)

---

**STRING 5:** "a+b" (3 characters)

| Char | ASCII | Class |
|------|-------|-------|
| a | 97 | 6 |
| + | 43 | 1 |
| b | 98 | 6 |

**F("a+b") = (0, 0.333, 0, 0, 0, 0, 0.667, 0)**

Parse tree:
```
  B+
 /  \
V(a) V(b)
```
Node types: V=2, B+=1, N=0

**τ("a+b") = (2/3, 1/3, 0, 0, 0) = (0.667, 0.333, 0, 0, 0)**

---

**VERIFICATION:**
```
F("1+2") = (0, 0.333, 0.667, 0, 0, 0, 0, 0)
F("a+b") = (0, 0.333, 0, 0, 0, 0, 0.667, 0)

τ("1+2") = (0, 0.333, 0, 0, 0.667)
τ("a+b") = (0.667, 0.333, 0, 0, 0)
```

F differs (digits vs lowercase). τ differs (numbers vs variables). No collision.

**Product distance:**

STEP 1: d_F(F("1+2"), F("a+b"))
```
√(0×0) = 0
√(0.333×0.333) = 0.333
√(0.667×0) = 0
√(0×0) = 0
√(0×0) = 0
√(0×0) = 0
√(0×0.667) = 0
√(0×0) = 0
Sum = 0.333
d_F = 2×arccos(0.333) = 2×1.231 = 2.462
```

STEP 2: d_F(τ("1+2"), τ("a+b"))
```
√(0×0.667) = 0
√(0.333×0.333) = 0.333
√(0×0) = 0
√(0×0) = 0
√(0.667×0) = 0
Sum = 0.333
d_F = 2×arccos(0.333) = 2.462
```

STEP 3: Product
```
d² = (2.462)² + (2.462)² = 6.061 + 6.061 = 12.122
d = √12.122 = 3.482
```

**VERIFY on calculator:**
```
sqrt( (2*arccos(1/3))^2 + (2*arccos(1/3))^2 )
```