# Closure of Star-Free Languages under Substitution

Let $L$ be a star-free language over finite alphabet $\Sigma$. A substitution will be a map $\sigma : \Sigma \to \mathcal{P}(\Sigma^*)$. It seems obvious that if $\sigma(a)$ is star-free for every $a \in \Sigma$, then $\sigma(L)$ will be star-free.
($\sigma(L) = \{ w_1 ... w_n | w_i \in \sigma(a_i) \land a_1 \ldots a_n \in L \}$) Take a star-free regular expression for $L$, and substitute star-free expressions for $L_i$ for each $a_i$ in that expression. The result will still be a star-free expression.

Now, my question is this: why is the following not a counterexample? $\Sigma = \{ 0, 1 \}$. $L = 1^*$ and $\sigma(1) = 0^* 1 0^* 1 0^*$. Both of these languages are star-free: $L = L( (\emptyset^c 0 \emptyset^c )^c )$ and similar tricks can be given to show that $\sigma(1)$ is star-free.

Now, the reason it seems like a counterexample: a word in $L$ contains only 1s. The substitution replaces each 1 with a word from a language whose words contain exactly 2 1s. So won't $\sigma(L)$ be the set of words with an even number of 1s, which is known to be non-star-free?

(Note: my proof suggestion of closure under substitution is a bit sketchy. The star-free expression for $1^*$ only has 0s in it. But I could then substitute the star-free expression for $\sigma(1)$ under a complement, no?)

• Star-free expressions use Boolean operators. Isn't the problem that $\sigma(K\cap L) \neq \sigma(K) \cap \sigma(L)$? – Hendrik Jan Jun 8 '13 at 22:59

I do not understand your proof sketch. Where do you want to subtitute $\sigma(1)$ under a complement. The only thing substituable in the star-free expression for $1^*$ is $0$. But 0, or $\sigma(0)$ is an independent element in the substitution, it is in no way related to the complement of $\sigma(1)$. So this can in no way make a proof.

Actually, if there was such a closure property, it should be easy to find in the literature on star-free RE. But all closure results under substitution put constraints on the type of substitution, such as being length preserving, or being injective. See in particular papers by Jean-Eric Pin and others.

Also,Pin defines star-free substitutions on $\Sigma$ as requiring an additional property, namely that $(\sigma(\Sigma))^*$ is star-free. (though I did not check the precise role of this property)

It seems that you have just proved that star-free languages are not closed under star-free substitution as you define it.

This does not seem too surprising, since non injective substitution does not in general commute with complement or distribute with intersection.

Among other papers:
Jean-Eric Pin, H. Straubling, and D. Thérien. Some results on the generalized star-height problem. May 12 2002.

• Thanks! I had trouble finding any mention of whether or not SF languages were closed under substitution except for passing reference in these slides that they were. That threw me for a loop since I thought my case was a counterexample. I should clarify: the bit about substituting the complement of $\sigma(1)$ was motivated by an application I have in mind. – Shane Steinert-Threlkeld Jun 9 '13 at 0:37