Grammar derivation tree
Generate a small formal language and preserve each replacement in a tree.
Adult planning suggestion: about 9–12 · Logic & rule checking
- Players
- 1–4 with adult support
- Time
- 15–25 minutes
- Materials
- S,a,b labels and branching tree space
Prepare
Use exactly the grammar S→aSb or S→ab. Start from S. Lowercase a,b are terminal symbols and cannot be rewritten. There is exactly one S at any unfinished stage, so no parallel replacement convention is needed.
Play
Choose S→aSb twice, then S→ab. The stages are S, aSb, aaSbb, aaabbb. Show which S was replaced each time and keep existing terminal order.
Worked example
Make a tree whose root S has children a,S,b for each recursive use, with final S children a,b. Reading terminal leaves from left to right gives aaabbb. Do not read internal S labels into the output.
Finish and check
The grammar generates a^n b^n for positive n: n a symbols followed by n b symbols, with at least one of each. abab has equal counts but cannot be generated because it breaks the required order. The empty string is not generated by either rule.
Adaptation and limits
Finish by drawing trees for ab,aabb and aaabbb and explaining why abab is excluded. This is a deliberately small formal grammar, not a complete grammar of English or Chinese. Stop before treating count equality alone as a valid derivation.
Purpose, observation and provenance
Within this activity: Generate a small formal language and preserve each replacement in a tree.
Ask learners to read only terminal leaves left to right and show why equal letter counts alone do not generate abab.
Our rules, examples and printable diagrams are separately prepared. The earliest inventor of the broader mechanism is not established here.
OpenDSA: Introduction to Formal Languages — Reference supports the stated concept; our fictional numbers, instructions and paper diagrams are independently prepared, not reproduced teaching pages.
Secondary practice: Cooperation and explaining a check.
For a class of 30, use ten groups of three. Prepare one player-material set per group and keep the host key with the adult. Rotate operator, recorder and checker after each worked example; a reader or scribe may help without choosing answers. Avoid public ranking or diagnostic labels.
Age bands are planning suggestions. Background references may address older learners and do not validate suitability for this age band. Goals describe observable actions, not measured long-term gains or institutional endorsement.
Free alternative: Copy the supplied grids, labels and cards onto reused paper. No specialist product is needed. Adults may prepare pieces or act as a scribe.
Printable materials
Preview at 100% scale, with browser headers and footers off. Cut with suitable help. Keep host keys separate. This is a manual tabletop kit, not an online opponent, automatic judge or solver.
Rules to keep beside the materials
- Use exactly the grammar S→aSb or S→ab. Start from S. Lowercase a,b are terminal symbols and cannot be rewritten. There is exactly one S at any unfinished stage, so no parallel replacement convention is needed.
- Choose S→aSb twice, then S→ab. The stages are S, aSb, aaSbb, aaabbb. Show which S was replaced each time and keep existing terminal order.
- Make a tree whose root S has children a,S,b for each recursive use, with final S children a,b. Reading terminal leaves from left to right gives aaabbb. Do not read internal S labels into the output.
- The grammar generates a^n b^n for positive n: n a symbols followed by n b symbols, with at least one of each. abab has equal counts but cannot be generated because it breaks the required order. The empty string is not generated by either rule.
- Finish by drawing trees for ab,aabb and aaabbb and explaining why abab is excluded. This is a deliberately small formal grammar, not a complete grammar of English or Chinese. Stop before treating count equality alone as a valid derivation.
Grammar derivation tree — player materials
| Stage | Whole string | Replaced S |
|---|---|---|
| 0 | S | |
| 1 | ||
| 2 | ||
| 3 |
| Target | Tree / derivation space |
|---|---|
| ________ | ________ |
| ________ | ________ |
| ________ | ________ |
| ________ | ________ |
| ________ | ________ |
| ________ | ________ |
Host check — keep separate
S→aSb→aaSbb→aaabbb; abab and empty string excluded.
Examples are stipulated model cases, not measured experimental or learning outcomes.