If $L$ is a regular language, then $s(L)$ is also regular

...where $s$ is a substitution that replaces each symbol of each string in $L$ with a regular expression.

For example, if $L=a^b$ and $s(a) =ab, s(b) = b^$, we have $s(L) = (ab)^b^$.

My thoughts so far are that replacing characters in a regular expression with regular expressions still gives us a regular expression overall. Namely I can show for $x \in L$ that $s(x)$ will be a regular set, and then I can do a union over $s(x)$ for all $x \in L$ to show $s(L)$ is regular (by closure of union).

My problem here is carefully showing the substitution will produce a regular set. Does it suffice to say if $x$ is something captured by a regular expression, then $s(x)$ is regular as well? I'm not sure how to prove this.

First thing you must understand is that regular expression are closed under union(+), closure(*) and concatenation (.) . reason being every regex denotes a regular language and regular languages are closed under union, closure and concatenation.

Second thing you should know that if r1 and r2 are regex then the following regex are also regular

• r1 + r2

• r1.r2

• r1 ,r2

so if you are substituting a regex by another regex it should fall among the above three categories or in simple words you will be able to form the regex(after substitution) with use of above relation. coming to you question the language generated after substitution can be formed using above closed properties over regex. let say r1 = a , r2 =b then we have

( ((r1.r2) ) . r2 ) making it regular

one more thing the only operation defined to regex are the above three and if so any substitution of regex by regex will have
either of the three operation associated with it thus making it regular again

StackExchange Computer Science Q#97931, answer score: 2