Formal definition of string to string substitution in a string

33 Views Asked by At

This question is related to my previous one, here: Formal definition of string-to-term substitution. Let $A$ be a nonempty alphabet. Also, let $s$ be a nonempty string, and let $t$ be any string, possibly empty. I want to define the notion of substituting $t$ for $s$ in a string. Let me give a few examples. Let our alphabet be $\{a,b,c\}$. Let $s$ be $bab$, and let $t$ be $cc$. In the string $babab$, it becomes $cccc$. As you can see, if there is overlap in a string, we just concatenate them. To give another example, if $s$ is $bb$ and $t$ is $cc$, then the string $bbbb$ becomes $cccccc$. Is it clearer now? My question is, given a string $t$ and a nonempty string $s$, what is the formal definition of the function on $A^*$, the Kleene closure of $A$, that substitutes the string $t$ for $s$ in every string in $A^*$?