Submission Codes: A Regex That Passes Every Test It Was Given
The Ministry's computer-science unit issues submission codes that students type into an exam scanner. A code is a string over the two characters A and B. The scanner's rulebook says: a code is valid only if, reading from left to right, the number of B's never exceeds the number of A's seen so far, and at the end the two counts are equal - so "AABB" and "AABABB" are valid while "ABBB" and "AAB" are not. The scanner hardware refuses any code longer than 60 characters. A developer implemented validation with the regular expression ^(A+B+)+$ and two unit tests passed. A teacher then submitted the code ABBB, which the scanner accepted, and a review meeting was called. The team lead argues that the code is "just a stack count, ten lines, no regex needed"; a colleague replies that "if it can be written as a regular expression it must be a regular language, so a finite automaton is enough".
1. Prove that the language L of valid codes over {A,B} is not regular, using the pumping lemma.
Read the worked answer
Claim. L = { w ∈ {A,B}* : every prefix of w has #A ≥ #B, and |w|_A = |w|_B } is not regular.
Proof by contradiction. Assume L is regular and let p be its pumping length. Choose w = A^p B^p. Then w ∈ L: every prefix has at least as many A's as B's, and the totals are equal.
By the pumping lemma, w = xyz with |xy| ≤ p, |y| ≥ 1, and xy^k z ∈ L for every k ≥ 0. Because |xy| ≤ p, the prefix xy lies entirely inside the initial run of A's, so y = A^m with m ≥ 1.
Take k = 2: xy²z = A^(p+m) B^p. The counts are no longer equal (p+m A's against p B's), so xy²z ∉ L. Equivalently, take k = 0: xy⁰z = A^(p−m) B^p has a prefix with more B's than A's, so it too is outside L. Either choice contradicts the lemma's claim that all pumped strings are in L.
Hence L is not regular. ∎
Why the witness was chosen this way. The decomposition must be forced into a single letter: if the witness mixed A's and B's inside the first p characters, y could straddle the boundary and the argument would have to case-split. Anchoring w at A^p B^p makes y necessarily a block of A's, which is the whole point of the proof.
2. Characterise exactly the language the expression ^(A+B+)+$ defines, and explain why the developer's test suite could not detect the bug. Which tests were missing?
Read the worked answer
What the regex accepts. (A+B+)+ matches one or more blocks, each a non-empty run of A's followed by a non-empty run of B's. So the language is A^{a₁}B^{b₁}A^{a₂}B^{b₂}…A^{a_m}B^{b_m} with m ≥ 1 and every aᵢ, bᵢ ≥ 1 - strings whose runs strictly alternate, starting with A and ending with B.
This is a strict superset of L. ABBB is accepted (a=1, b=3) yet is invalid. But every valid code is accepted: in a valid code the runs must alternate, must start with A (otherwise the first B has no A before it) and must end with B (equal totals). The regex therefore never rejects a good code and sometimes accepts a bad one.
Why the tests were green. Both unit tests, AABB and AABABB, are positive examples. A test suite built only from valid inputs measures false rejections; it is structurally incapable of detecting over-acceptance. This is the general lesson: for a recogniser, the negative cases carry the specification.
Missing tests. Minimal boundary negatives: ε, B, A, ABBB, AAB, BA, ABAB (valid, include as positive), AABABB (valid), AAABBB (valid, but note it is a different shape from AABB), plus a near-miss pair such as AABABB versus AABBBA. Add property-based generation if available, and assert both directions - accepted ⇒ valid, and valid ⇒ accepted - because only the conjunction pins down the language.
On the colleague's argument. It is half right and dangerously so. "The regex defines a regular language" is true; "therefore the intended language is regular and an automaton suffices" does not follow. The regex defines a different language from the one in the rulebook, and by the previous proof no expression over {A,B} can define L at all.
3. The 60-character hardware cap is guaranteed. Does that make the validation problem regular, and should the team replace the counter with a finite automaton? Advise.
Read the worked answer
Yes, the capped language is regular - for a trivial reason. L∩{A,B}^{≤60} is a finite set of strings, and every finite language is regular. You could even write it out as a finite union of literal strings. But "regular" is a statement about existence, not about size.
What a DFA would actually cost. To accept valid codes of exactly length 60, a state must remember both how many characters have been read (0…60) and the current balance (0…60), with balance ≥ 0 and balance ≤ 60 − position for the state to be completable. The reachable pairs (i, d) with d ≤ min(i, 60−i) number roughly Σ(i+1) over i = 0…60 ≈ 1,900, plus a dead state for a prefix with more B's than A's and a trap for length 61. That is a table of ~1,900 rows to reproduce six lines of logic - more code, more opportunities for a transcription error, and no runtime benefit at these input sizes.
Recommendation: keep the counter. Scan left to right with an integer: increment on A, decrement on B, reject immediately if it goes negative, accept only if the length is ≤ 60 and the counter ends at 0. This is O(n) time, O(1) memory, and it works without the cap, so the cap is a hardware limit rather than a load-bearing part of the algorithm - if the scanner is ever upgraded, the checker is already correct.
What the team lead got right and wrong. "Ten lines, no regex" is the correct engineering call. Calling it "just a stack" is imprecise for this language - a single integer counter is enough; a stack becomes necessary as soon as the alphabet grows to two kinds of brackets or the rulebook distinguishes nesting types. Write the counter to be replaced by a stack, not to pretend it already is one.
The real integrity issue is that the specification and the checker disagreed for a full release. Whatever the implementation, the acceptance criteria from the rulebook must be encoded as executable tests in both directions before the next submission window.