FREE CONTRIBUTION CHRONOLOGY · c. 5th–4th century BCE

Rules that generate

How can a finite rule system generate an enormous set of valid expressions?

The historical question

A list can preserve known expressions, but it cannot explain how to construct a new valid one. Pāṇini’s grammar compresses linguistic knowledge into ordered symbolic transformations, contexts, exceptions, and meta-rules.

A generative system stores procedures and constraints instead of enumerating every possible output.

A grammar describes a family of outputs

Consider the artificial grammar S → aS | b. A derivation S → aS → aaS → aab generates aab. Every terminating derivation contains zero or more a symbols followed by exactly one b. This is an invariant of the construction: recursive expansion adds an a and preserves one pending S; the terminal rule replaces that final S with b. A list of examples could miss a new string; the grammar explains how every member is constructed.

Generation and recognition are different tasks. A generator chooses productions. A recognizer receives a finished string and decides membership. For this grammar, scan through any initial a symbols, then require exactly one final b. The procedure rejects aba because there is input after the b. It also rejects an empty string. A language description, an algorithm for recognition, and the runtime cost of that algorithm are separate objects.

Rule conflicts introduce another requirement. If two transformations match the same intermediate form, their ordering may change the output. A specification must define precedence, allow multiple outcomes, or prove the order irrelevant. This is a useful connection to Pāṇini’s technical rules and metarules. The artificial grammar here is not Sanskrit and does not establish that ancient grammar is identical to a compiler.

What the evidence does not establish

The dating of Pāṇini is uncertain. Teach the formal mechanism and avoid turning a deep linguistic tradition into the slogan “first compiler.”

Reconstruction exercise

Modify the grammar to generate exactly the strings with one or more a symbols followed by b. Derive aaab and explain how your recognizer rejects b.

Worked solution

Use S → aT and T → aT | b. The first rule forces an a. Derive S → aT → aaT → aaaT → aaab. The recognizer first requires one a, consumes any additional a symbols, and then requires a single b with no remaining input. The original grammar accepts b; the new grammar does not. This boundary test distinguishes the languages.

Test the limits and transfer the idea

1. Derivation and proof · allow 30 minutes

Prove what a recursive grammar generates

Consider the artificial grammar S → aSb | c. Derive aacbb. Prove that every terminating derivation produces aⁿcbⁿ for some n≥0, and that every such string has a derivation. Give a linear-time recognizer and explain why merely counting equal numbers of a and b would wrongly accept some strings. This is an original formal-language exercise, not Sanskrit grammar.

Get a starting hint

Track the pending S and the symbols accumulated on its two sides; prove both inclusion directions.

Compare your reasoning with the worked solution

A derivation is S → aSb → aaSbb → aacbb. After k recursive productions, the intermediate form is aᵏSbᵏ; this invariant holds initially and one more recursive production preserves it. Replacing S with c ends with aᵏcbᵏ. Conversely, n recursive steps followed by the terminal rule construct every aⁿcbⁿ. A recognizer counts an initial run of a, requires one c, then consumes exactly that many b and requires end of input. It rejects other symbols, a second c and missing symbols. Each input position is inspected a constant number of times, giving linear time. Counting alone wrongly accepts bac because order is also part of the language. The MacTutor biography is later scholarship about Pāṇini, not primary evidence that this toy grammar reproduces his rules.

Check your reasoning

Proves both that outputs have the form and all such forms are generated.
Specifies order, count and end-of-input checks.
Separates formal illustration from historical grammar.

2. Counterexample and specification · allow 25 minutes

Terminating rewrite rules can still disagree

A toy rewriting system has rules ab → x and bc → y. Starting from abc, show the two possible final strings. Prove that rewriting always terminates on finite input, but explain why termination does not ensure a unique result. Define one deterministic priority policy and one observable test for it. Explain why assigning a policy in this exercise does not prove how a particular ancient grammatical rule conflict was resolved.

Get a starting hint

Each rewrite shortens the string. Check overlapping matches before assuming rules commute.

Compare your reasoning with the worked solution

Applying ab first gives xc; applying bc first gives ay. Neither string contains another left-hand-side match, so both are final and unequal. Every rewrite replaces two symbols with one, strictly decreasing the finite nonnegative length, which proves termination. Uniqueness requires an additional property such as confluence or an explicit selection policy; it does not follow from that measure. A leftmost-match policy chooses ab in abc and returns xc. A regression test with abc distinguishes it from a rightmost policy, which returns ay. Other strings should test repeated matches and overlaps. Historical attribution requires the actual grammatical text and scholarly interpretation of its technical conventions; a modern rewrite counterexample establishes a logical distinction, not an undocumented historical mechanism.

Check your reasoning

Produces both normal forms and a decreasing termination measure.
Distinguishes termination, confluence and deterministic priority.
Limits the historical inference to what actual textual evidence could support.

Check your understanding

Which string belongs to S → aS | b?

Explanation

Sources and further reading

Pāṇini: MacTutor History of Mathematics · University of St Andrews