# Finite substitution and regular closure properties

I'm not sure if I get the following definition right:

1.Def: A map $\varphi: \Sigma^{*} \rightarrow 2^{\Delta^{*}}$ is called Substitution iff:

1. $\forall u,v \in \Sigma^{*}: \varphi(uv)=\varphi(u) \varphi(v)$
2. $\varphi(\epsilon)=\{\epsilon\}$

My assumption: every string in $\Sigma^{*}$ with the size $>0$ maps to a Language from $\Delta^{*}$.

such as:

$\Sigma := \{a, b\}$, $\Delta:=\{0,1\}$

$\varphi(a) = \{01^{i}0 |i \in \mathbb N \}$, $\varphi(b) = \{w\in \Delta^{*} ||w|_{0} \neq |w|_{1}\}$

$\varphi(ab) = \varphi(a)\varphi(b)=\{01^{i}0w |i \in \mathbb N \land w \in \Delta^{*} |w|_{0} \neq |w|_{1}\}$

example strings: 001, 000, 0101, 01011, 010100, ...

My first question: Is this assumption and example right?

2.Def: $\varphi$ is finitie iff $\varphi(a)$ $\forall a \in \Sigma$ is a finite subset of $\Delta^{*}$

My assumption: $\Delta^{*}$ is every possible string over the alphabet $\Delta$ and an finite subset would be a limited set $X \subseteq \Delta^{*}$ $|X| < \infty$

I would now implie that my first example is not a finite substitution, because a and b are not mapping to finite sets.

an example could be:

$\varphi(a) = \{10^{i}1 | i \in \{1,...,100\}\}$, $\varphi(b) = \{\epsilon\}$

$\varphi(bba) = \varphi(b)\varphi(b)\varphi(a) = \{\epsilon\}\{\epsilon\}\{10^{i}1 | i \in \{1,...,100\}\}=\{10^{i}1 | i \in \{1,...,100\}\}$

now I can implie that the class $REG$ is closed under finite substitution, because a concatenation of finite sets is finite and every finite set is regular.

My second question: Is this my assumption about finite substitution and the closure propierty right?

• $L := \{ab^{n}a | n > 1\}$ The $RE$ would look like this: $RE_{L} = (ab^{+}a)$ $\varphi : \varphi(a)=\{100, 1100\}, \varphi(b)=\{1,0110\}$ $\Rightarrow \varphi(RE_{L}) = ((100(1 |0110)^{+}100) | (1100(1 |0110)^{+}100)|(1100(1 |0110)^{+}1100)|(100(1 |0110)^{+}1100))$ the resulting $RE$ is the combination of all words produced by the substitution. Conclusion: Iff the substitution is finite there is an $RE$ for the image of the mapping. Mar 4 '17 at 14:05