Sat, 17 Nov 2007 10:10:14 +0100

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: | "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> |

Newsgroups: | comp.compilers |

Date: | Sat, 17 Nov 2007 10:10:14 +0100 |

Organization: | cbb software GmbH |

References: | 07-11-048 |

Keywords: | parse, theory |

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.