A hand-written validator and a written grammar disagree about one input string — how does exhibiting a derivation settle it?

## The disagreement, stated precisely A team writes its saved-filter expression language down as a rule set. Separately, a hand-written validator in the product decides which filters users may save. A user reports that a filter the documentation implies is legal gets rejected. There are now two artefacts that claim to define the same language, and they differ on at least one string. Before anything is fixed, the disagreement needs to be turned into a checkable claim. A derivation does that, and the direction of the evidence is the whole point. ## Exhibiting a derivation proves membership Membership in the language a grammar defines means exactly one thing: there is a sequence of rewriting steps from the start symbol to the string, where each step replaces one nonterminal occurrence by the right-hand side of one of its productions. Producing such a sequence is a complete proof. It is checkable line by line by anyone, it needs no tooling, and it does not depend on any parser existing. So the procedure is: 1. Write the disputed string out as terminals. 2. Start from the start symbol and try to reach it, choosing alternatives as needed. Writing the derivation in a fixed order — always rewriting the leftmost nonterminal, say — keeps the attempt systematic and makes the result easy for a reviewer to follow. 3. If you reach the string, you are done: the grammar generates it, and the validator's rejection is a discrepancy with the spec. ## Failing to find one proves much less The reverse direction does not hold by symmetry, and this is where candidates most often go wrong. Not having found a derivation can mean the string is not generated, or it can mean you took a wrong alternative three steps in and gave up. A hand search explores one path at a time and a rule set with several alternatives per nonterminal has many paths. What rescues the negative claim is that membership for a context-free rule set is **decidable**: there are algorithms that answer yes or no for any grammar and any input string, one classical example being the CYK algorithm, which runs in time cubic in n, the number of terminals in the input string, for a grammar in a suitably normalised form. The existence of a decision procedure is the licence for asserting non-membership; your own failed search is not. | Observation | What it establishes | What it does not establish | |---|---|---| | A derivation written out | the string is in the language, definitively | anything about which artefact is right | | A failed hand search | that this attempt did not succeed | that no derivation exists | | A decision procedure answering no | the string is not in the language | that the grammar matches the team's intent | | The validator rejecting the string | how the deployed code behaves today | anything about the specification | ## Then the judgement call, which is not formal Once the formal fact is settled, the interesting question starts. Suppose the derivation exists and the validator rejects the string. Exactly one of these is true, and deciding which is a team decision, not a mathematical one: - **The validator is wrong.** The rule set expresses what the team intended; the code has a gap. Fix the code, and add the string as a regression case. - **The grammar is wrong.** The rule set generates more than the team meant to allow — perhaps it permits a nesting or a combination nobody wants to support. Fix the rule set, and note that the validator was accidentally right. Saying which artefact is authoritative *before* the next disagreement is the durable fix. A written rule set that nothing checks against will drift from the code within a release or two; a validator with no written specification cannot be reviewed at all, only re-read. Teams that keep both usually do one of two things: generate the check from the rule set, or keep a shared corpus of accepted and rejected strings that both artefacts are tested against. ## What a strong answer sounds like The candidate separates three layers without being prompted: the **formal** layer (a derivation proves membership; its absence proves nothing on its own, though membership is decidable), the **engineering** layer (which artefact is the specification, and what keeps them in step), and the **product** layer (whether the team actually wants that string to be accepted at all). A weak answer collapses them, usually by treating the deployed validator's behaviour as the definition of the language — which makes the rule set decorative and the disagreement unresolvable.