# Balanced words through length 6

KL-FCS-032 · Formal languages · version 1.0.0

## Problem

List every balanced parenthesis word of length at most 6, including the empty word.

## Context

Characterize bounded membership in a recursively structured language while keeping the length bound visible.

## Definitions

- **Dyck word**: A balanced parenthesis string whose prefix balance never goes negative.
- **Prefix balance**: Opening parentheses minus closing parentheses in an input prefix.
- **Membership**: Whether a particular word belongs to the specified language.

## Checked result

Accepted words: 9.

A prefix can invalidate a word before its final symbol. The accepted list includes different nesting structures and concatenations, not only fully nested strings.

## Checker reasoning

1. Generate every parenthesis string up to the stated length.
2. Scan each prefix and reject any negative balance.
3. Accept only strings with terminal balance zero.
4. Compare the complete accepted-word list and its cardinality.

## Dataset construction

{
  "family": "formal-languages",
  "task": "List every balanced parenthesis word of length at most 6, including the empty word.",
  "input_encoding": "Structured JSON; field meanings are stated in the specification.",
  "coverage": "Complete bounded membership · 127 candidates",
  "acceptance": [
    "Generate every parenthesis string up to the stated length.",
    "Scan each prefix and reject any negative balance.",
    "Accept only strings with terminal balance zero.",
    "Compare the complete accepted-word list and its cardinality."
  ],
  "generation": "Deterministic finite fixture; full enumeration or witness replay as stated.",
  "split_policy": "Reference corpus for exposition and reproduction; no train/test evaluation split is claimed."
}

## Formal payload

```json
{
  "specification": {
    "max_length": 6,
    "alphabet": [
      "(",
      ")"
    ],
    "language": "Every prefix has nonnegative balance and the terminal balance is zero."
  },
  "claim": {
    "accepted_count": 9
  },
  "witness": {
    "words": [
      "",
      "()",
      "(())",
      "()()",
      "((()))",
      "(()())",
      "(())()",
      "()(())",
      "()()()"
    ]
  }
}
```

## Complexity

A length bound n produces 2ⁿ⁺¹−1 candidate words; each membership scan takes O(n).

## Limits

This enumerates a bounded language slice; it is not a grammar-equivalence theorem.

## Common error and further work

Equal numbers of opening and closing symbols do not guarantee proper nesting.

Add context-free grammar membership, CYK charts, and parse-tree certificates.

## Verification

Complete bounded membership · 127 candidates. 127 checker units.
Replay with `python3 tools/verify.py`. Mechanical status: checked; human review
has not yet been recorded. Custom Python verification, not a proof-assistant
claim. Checker 1.0.0 and exact source hashes are in `verification.json`.

## Provenance and references

Original Kenton Labs reference instance, authored with Codex assistance on 2026-10-11.
No external dataset or model-generation experiment. Reuse-license selection
remains pending.

- [Conceptual reference](https://ocw.mit.edu/courses/18-404j-theory-of-computation-fall-2020/download/)