Unconditional Replacement

The unconditional replacement of A by B is written 
A -> B
where A and B are any regular expressions that define simple regular languages. We define this replacement expression as 
[no_A [A .x. B]]* no_A]
where no_A abbreviates ~$[A - []], i.e. the complement of any string that includes A minus the empty string. Note that if A does not contain the empty string, then 
~$[A - []]   =   ~$[A]
On the other hand, if A does contain the empty string, ~$[A] is null whereas ~S[A - []] at least contains the empty string. We need the latter language in our definition to get the intended meaning for A -> B The definition of -> describes a regular relation whose members contain zero or more iterations of [A .x. B], possibly alternating with strings not containing A that are mapped to themselves.

Checkpoints

  1. Convince yourself (using xfst that if A and B denote singleton sets, then the relation [A .x. B] implements a function that maps A to B.

  2. Define (without the replace operator) the regular expression that maps a, b, and c to x, y, and z respectively. Show that it works in both directions.
[Wed Mar 29 09:07:51 2000]