Try
A small synthetic log-filter language records only repeated occurrences of one marker, a. A run of length n is the word aⁿ; length zero is the empty word ε. A filter is a set of accepted words, called a language. Its universe U consists of every finite run, including ε.
The filter editor offers three constants: the empty language ∅, the singleton ｛ε｝, and the singleton ｛a｝. You may combine expressions by union, complement relative to U, and concatenation. Every expression must be a finite tree built with these operations. Repeating an operation an unspecified number of times is not an additional permitted constructor.
Can this editor accept exactly the runs whose lengths have remainder one on division by three? A scanning program could count modulo three. That observation does not yet produce an expression in this particular editor. Our goal is to prove a limitation of its expression vocabulary, rather than report that several attempted expressions failed.
Predict
Distinguish the object ε from the language ｛ε｝. Concatenating a word with ε leaves it unchanged. Concatenating a language with ｛ε｝ therefore leaves that language unchanged; concatenating it with ∅ gives ∅ because no factor can be selected from the empty set.
A language is finite when it contains finitely many words. It is cofinite when its complement in U is finite. On this unary alphabet, cofinite means all sufficiently large lengths are accepted. It does not require every earlier length to be excluded. Predict whether union, complement and concatenation preserve the property “finite or cofinite.” Try especially the case in which a finite operand is empty: choosing one of its elements would be an invalid proof step.
Experiment
Build a worked filter A accepting lengths zero and three. Its expression is ｛ε｝ union three concatenated copies of ｛a｝. Build B as the complement of the singleton length one. Before reading the table, determine which lengths AB accepts. Concatenation adds lengths, but one resulting word can have more than one factorization.
| Length | A | B | AB | Remainder-one target |
|---|
| 0 | yes | yes | yes | no |
|---|
| 1 | no | no | no | yes |
|---|
| 2 | no | yes | yes | no |
|---|
| 3 | yes | yes | yes | no |
|---|
| 4 | no | yes | yes | yes |
|---|
| 5 | no | yes | yes | no |
|---|
| 6 | no | yes | yes | no |
|---|
In fact AB=B: the zero-length factor already produces all of B, while adding three to an accepted B length never produces the sole missing length one. Length three has two factorizations, 0+3 and 3+0. Counting factor pairs would count its single output word twice.
Change A to ∅, then to ｛ε｝, without changing B. Explain both resulting languages from their definitions. Finally extend the table through length ten. A longer table remains finite evidence; the proof below covers arbitrary expression depth and every length.
Understand
Prove closure before invoking induction
Identify a unary language with its set of lengths in the nonnegative integers. Concatenation becomes the sumset A+B, consisting of all i+j with i in A and j in B. This identification uses the one-letter alphabet: there is exactly one word of each length.
Complement exchanges finite and cofinite sets. A union of two finite sets is finite. If either operand is cofinite, the complement of their union is a subset of a finite complement, so their union is cofinite. These arguments cover every Boolean-operation case.
For concatenation, first handle an empty operand: the result is empty. Two finite operands have only finitely many factor pairs, hence finitely many sums. Now suppose A is finite and nonempty, and B includes every length at least N. Choose any r in A. Every n≥r+N can be written r+(n−r), with n−r in B, so the sumset contains a complete tail. It is cofinite. If instead B is finite and nonempty while A contains all lengths at least N, choose s in B and use threshold N+s. This explicitly handles both operand orders.
Finally suppose A contains all lengths at least N and B all lengths at least M. Every n≥N+M is N+(n−N), with the first term in A and the second in B. Thus A+B is cofinite. These are sufficient thresholds, not necessarily minimal ones. The finitely many earlier lengths can include some accepted words; our conclusion does not assert that the result is exactly a tail with no exceptions.
Lift the invariant to every expression
The three constant expressions denote finite languages. Assume the property for the child expressions of a constructor. The preceding closure arguments prove it for their union, complement or concatenation. Structural induction on the finite syntax tree now establishes that every permitted expression denotes a finite or cofinite language. The induction concerns expressions, not a presumed list of all resulting languages; different expressions may denote the same language.
The target includes lengths 1,4,7,… and excludes lengths 0,3,6,…. Both collections are infinite. It is neither finite nor cofinite, so the invariant rules out every expression in the stated grammar. This conclusion does not rest on the failure of a search through small expressions.
An invariant normally supplies only a necessary condition. Here a converse can be proved separately: length n has a singleton expression made from n copies of ｛a｝, with ｛ε｝ used for n=0. Finite unions describe every finite language, and ∅ supplies the empty case. Complementing an expression for a finite excluded set describes every cofinite language. Thus this particular grammar denotes exactly the finite and cofinite unary languages. The converse required a construction; it was not automatic from preservation.
Apply
Choose a testing cutoff M. List the target’s accepted lengths up to M and construct the finite union of their singleton expressions. This filter agrees with the target throughout the test range. Nevertheless, it rejects every word longer than M, while the target accepts infinitely many such words. Explain why passing every test in a finite prefix cannot establish global equivalence.
Now add a new grammar constructor, star. For a language L, L∗ permits concatenating any finite number of its words, including zero words. The zero-fold product contributes ε. Let C be the singleton length three. Then C∗ accepts lengths divisible by three, and ｛a｝C∗ accepts exactly the target. This is a valid expression in the extended grammar, not a counterexample to the old theorem. The old invariant fails at the new constructor: finite C can have a star that is neither finite nor cofinite.
Check the boundary languages: ∅∗=｛ε｝, because only the zero-fold product contributes a word; ｛ε｝∗=｛ε｝, because every concatenation remains empty. Do not confuse either result with ∅.
For a separate computational solution, scan the input word while maintaining a remainder in three states. Start at zero, advance the remainder once per marker, and accept state one at the end. Every finite input terminates. This proves decidable membership without claiming an expression in the original grammar or that the star extension can express every possible language.
Continue
Return to generated sets and unique parsing for structural induction over constructions, or sets and double inclusion for membership-based equality arguments. Keep the alphabet, complement universe and permitted constructors explicit when transferring this proof. With more than one letter, many words share a length, so the sumset argument alone no longer identifies an entire language.
