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⁎⟶Nt be the corresponding Parikh morphism. Given two languages L1,L2⊆A⁎L1,L2⊆A⁎, we say that L1L1 is commutatively equivalent to L2L2 if there exists a bijection f:L1⟶L2f:L1⟶L2 from L1L1 onto L2L2 such that, for every u∈L1u∈L1, ψ(u)=ψ(f(u))ψ(u)=ψ(f(u)). Then every bounded context-free language is commutatively equivalent to a regular language.