Algebraic definition of word substitution?

Tegiri Nenashi <>
Fri, 16 Nov 2007 11:11:22 -0800 (PST)

          From comp.compilers

Related articles
Algebraic definition of word substitution? (Tegiri Nenashi) (2007-11-16)
Re: Algebraic definition of word substitution? (Hans-Peter Diettrich) (2007-11-17)
Re: Algebraic definition of word substitution? (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


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

Post a followup to this message

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