# Algebraic definition of word substitution?

## Tegiri Nenashi <TegiriNenashi@gmail.com>Fri, 16 Nov 2007 11:11:22 -0800 (PST)

From comp.compilers

Related articles
Algebraic definition of word substitution? TegiriNenashi@gmail.com (Tegiri Nenashi) (2007-11-16)
Re: Algebraic definition of word substitution? DrDiettrich1@aol.com (Hans-Peter Diettrich) (2007-11-17)
Re: Algebraic definition of word substitution? mailbox@dmitry-kazakov.de (Dmitry A. Kazakov) (2007-11-17)
| List of all articles for this month |

 From: Tegiri Nenashi Newsgroups: comp.compilers Date: Fri, 16 Nov 2007 11:11:22 -0800 (PST) Organization: Compilers Central Keywords: theory, question Posted-Date: 16 Nov 2007 20:36:49 EST

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...

Post a followup to this message