Algebraic definition of word substitution?

Arguably word substitution is the most frequent operator in
programming. Yet I struggle to see how is it defined. Formally, given
a word over an alphabet of terminal symbols, say {a,b,c,...} how do
we derive a word where each occurrence of s is substituted with t?
Granted, we'd better think in terms of languages as sets of words, how
do we define an perator that transforms a language such that each word
is transformed with simple symbol substitution as above? Note, that it
is quite easy to do some other transformations:


Y = s X


prefix each word in "X" with "s". Or


Y = X + s


add the word "s" to language "X". Likewise, defining substitution at
the end (or the beginning) of the string is only marginally more
complex. For example, given the string


abs


and substitution "rule" s->t we first remove the "s" at the end by the
conjugate kernel ("division"), then join it with t. Of course, this
has
to generalize somehow to more complex expression substitutions like


a+ab -> ca + ac + a +c


and, more important, should handle occurrences in the middle of the
word...

Return to the comp.compilers page.
Search the comp.compilers archives again.