On commutative context-free languages

摘要

Let Σ = {a1, a2, …, an} be an alphabet and let L ⊂ Σ∗ be the commutative image of FP∗ where F and P are finite subsets of Σ∗. If, for any permutation σ of {1, 2, …, n }, L ∩ ασ∗(n) … aσ∗(n) is context-free, then L is context-free. This theorem provides a solution to the Fliess conjecture in a restricted case. If the result could be extended to finite unions of the FP∗ above, the Fliess conjecture could be solved.