On the commutative equivalence of bounded context-free and regular languages: The semi-linear case
This is the third paper of a group of three where we prove the following result. Let A be an alphabet of t  letters and let ?:A??Nt ? : A ? ? N t be the corresponding Parikh morphism. Given two languages L1,L2?A? L 1 , L 2 ? A ? , we say that L1 L 1 is commutatively equivalent to L2 L 2 if there exists a bijection f:L1?L2 f : L 1 ? L 2 from L1 L 1 onto L2 L 2 such that, for every u?L1 u ? L 1 , ?(u)=?(f(u)) ? ( u ) = ? ( f ( u ) ) . Then every bounded context-free language is commutatively equivalent to a regular language.
commutative equivalence bounded context-free language semilinear set