NotePiecewise testable languages via combinatorics on words

A regular language L over an alphabet A is called piecewise testable if it is a finite Boolean combination of languages of the form A∗a1A∗a2A∗…A∗aℓA∗, where a1,…,aℓ∈A, ℓ≥0. An effective characterization of piecewise testable languages was given in 1972 by Simon who proved that a language L is piecewise testable if and only if its syntactic monoid is J-trivial. Nowadays, there exist several proofs of this result based on various methods from algebraic theory of regular languages. Our contribution adds a new purely combinatorial proof.

► Simon's effective characterization of piecewise testable languages is studied. ► A new purely combinatorial proof of Simon's theorem is presented. ► The original estimate of Simon is slightly improved.