Chomsky counts mathematics as a language from the start: "the set of ‘sentences’ of some formalized system of mathematics can be considered a language" (SS p.13). On p.21 he states "(9) English is not a finite state language", meaning that "it is impossible, not just difficult, to construct a device" of that kind. For the simplest case, (10i), the strings ab, aabb, aaabbb…, he writes: "We can easily show that each of these three languages is not a finite state language." Then footnote 3 on p.22: CITED
Pullum (2011) read the book as a mathematical logician would. His verdict is that "SS contains no proof that English is beyond the power of finite state description", and that "Chomsky did not even attempt such a proof in SS". SS itself calls its argument "a rough indication of the lines along which a rigorous proof of (9) can be given" (p.23). CITED
Write "(" for Chomsky's a and ")" for his b. Language (10i) is then the set of strings with n opening brackets followed by n closing ones. Brackets.lean proves no_finite_reader: no reader with finitely many states accepts exactly those strings. KERNEL-CHECKED
This settles the footnote for brackets, which Chomsky said could "easily" be shown. It says nothing about English, which remains Pullum's point. MODEL
Parentheses are needed because notation without them is ambiguous. The script parses each expression with a grammar that has no precedence rules at all, and counts the trees: COMPUTED
| expression | one tree | the other tree |
|---|---|---|
| 6÷2(1+2) | (6÷2)(1+2) = 9 | 6÷(2(1+2)) = 1 |
| 1/2x, x = 3 | (1/2)·x = 1.5 | 1/(2x) = 1/6 |
| sin x/2, x = 1 | (sin x)/2 = 0.421 | sin(x/2) = 0.479 |
| 2^3^2 | (2³)² = 64 | 2^(3²) = 512 |
| 8/4/2 | (8/4)/2 = 1 | 8/(4/2) = 4 |
The viral "6÷2(1+2)" has exactly two readings, 9 and 1. Nothing in the string decides between them; only a convention about implicit multiplication does. The number of trees grows fast. With k plus signs in a row, "1+1+…+1" has 1, 2, 5, 14, 42, 132, 429, 1430 trees for k = 1…8, the Catalan numbers. "1+2*3-4/2" has 14 trees and 9 different values, and the school convention picks one of them, 5. COMPUTED
A context-free grammar is exactly the device that can hold both the brackets and the trees. Jurafsky and Martin call such grammars "the backbone of many formal models of the syntax of natural language (and, for that matter, of computer languages)" (SLP 3rd ed. draft, p.425). CITED
Chomsky's §3.3 concedes the other half: if nesting has a fixed limit, a finite machine suffices, because "a list is essentially a trivial finite state grammar" (SS p.23). The script collects every formula in the series' published pages ($…$, $$…$$, \(…\), \[…\]) and measures how deep the round and square brackets go: COMPUTED
| bracket depth | formulas |
|---|---|
| 0 | 8,824 |
| 1 | 2,822 |
| 2 | 157 |
| 3 | 5 |
No formula in the series goes deeper than three, and the deepest are on the Enceladus page. In practice, then, this series' notation could be checked by a reader with five states: depths 0 to 3 and a reject state. The grammar of mathematics is beyond finite machines, but the mathematics written here never uses that power. That is Chomsky's §3.3 observed in a real corpus. COMPUTED
See also Chapter 3 (a counting rule checked the same way), Chapter 5 (the corpus's own readers), the Chomsky gallery page and Book XIX ch 3 (Lean's own parser).