Fri, 16 Nov 2007 11:11:22 -0800 (PST)

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

From: | Tegiri Nenashi <TegiriNenashi@gmail.com> |

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

Return to the
comp.compilers page.

Search the
comp.compilers archives again.