Home > Archive > Compilers > November 2007 > Algebraic definition of word substitution?
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
Algebraic definition of word substitution?
|
|
| Tegiri Nenashi 2007-11-16, 10:13 pm |
| 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...
| |
| Dmitry A. Kazakov 2007-11-18, 4:39 am |
| On Fri, 16 Nov 2007 11:11:22 -0800 (PST), Tegiri Nenashi wrote:
> 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?
It is a ternary operation (per word symbol):
S x S x S --> S
---------------
a a a -> a
....
a s t -> a
b s t -> b
....
r s t -> r
s s t -> t
t s t -> t
....
z z z -> z
Maybe you want to split it into binary operations? If so, then you could
add the word 0 to the language and a pair of operations like * and +:
X * Y = 0 iif X=Y and X, otherwise
X + Y = Y iff X=0 and X, otherwise
Then (X * s) + t will do substitution s->t on X.
BTW, in image processing there are so-called ROPs (Raster Operations) which
serve similar purposes.
--
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de
|
|
|
|
|