# Formal languages

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.

## Acceptance procedure

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.

## Complexity

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

## Common failure

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

## Extensions

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

## Instances

- KL-FCS-031: Balanced words through length 4 — Accepted words: 4
- KL-FCS-032: Balanced words through length 6 — Accepted words: 9
- KL-FCS-033: Balanced words through length 8 — Accepted words: 23

## References

- https://ocw.mit.edu/courses/18-404j-theory-of-computation-fall-2020/download/